論文

査読有り
2000年5月

No feasible monotone interpolation for simple combinatorial reasoning

THEORETICAL COMPUTER SCIENCE
  • Noriko H. Arai

238
1-2
開始ページ
477
終了ページ
482
記述言語
英語
掲載種別
研究論文(学術雑誌)
出版者・発行元
ELSEVIER SCIENCE BV

The feasible monotone interpolation method has been one of the main tools to prove the exponential lower bounds for relatively weak propositional systems. Arai (Theoret. Comput. Sci. 170 (1996) 129-144) introduced a simple combinatorial reasoning system, GCNF+permutation, as a candidate for an automatizable, though powerful, propositional calculus. We show that the monotone interpolation method is not applicable to prove the superpolynomial lower bounds for Simple Combinatorial Reasoning. At the same time, we show that Cutting Planes, Hilbert's Nullstellensatz and the polynomial calculus do not p-simulate Simple Combinatorial Reasoning. (C) 2000 Elsevier Science B.V. All rights reserved.


リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000087413600016&DestApp=WOS_CPL
共同研究・競争的資金等の研究課題
命題論理の証明の長さに関する研究
URL
http://www.sciencedirect.com/science/article/pii/S0304397599001425
ID情報
  • ISSN : 0304-3975
  • Web of Science ID : WOS:000087413600016

エクスポート
BibTeX RIS