scientific article; zbMATH DE number 2080216

MaRDI QIDQ4472459zbMATH OpenFDO

Authors Jochen Messner, Johannes Köbler

Publication date 4 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1974/19740361.htm

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1738671
• Total nondeterministic Turing machines and a p-optimal proof system for SAT
• scientific article; zbMATH DE number 1136087
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• scientific article; zbMATH DE number 1342213

Cited in

(15)

• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• Total nondeterministic Turing machines and a p-optimal proof system for SAT
• Knowledge compilation languages as proof systems
• Further oracles separating conjectures about incompleteness in the finite domain
• An oracle separating conjectures about incompleteness in the finite domain
• Reductions between disjoint NP-pairs
• Optimal acceptors and optimal proof systems
• On slicewise monotone parameterized problems and optimal proof systems for TAUT
• On an optimal randomized acceptor for graph nonisomorphism
• scientific article; zbMATH DE number 1342213 (Why is no real title available?)
• scientific article; zbMATH DE number 1136087 (Why is no real title available?)
• scientific article; zbMATH DE number 1738671 (Why is no real title available?)
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• Speedup for natural problems and noncomputability
• Does subset sum admit short proofs?

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4472459)