Total nondeterministic Turing machines and a p-optimal proof system for SAT

DOI10.1007/978-3-319-58741-7_34MaRDI QIDQ2011675zbMATH OpenOpenAlexFDO

Authors Zenon Sadowski

Publication date 4 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-58741-7_34

zbMATH Keywords

disjoint NP-pairsoptimal propositional proof systemp-optimal proof system for SATtotal Turing machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of proofs (03F20) Classical models of computation (Turing machines, etc.) (68Q04) Computational aspects of satisfiability (68R07)

Recommendations

• scientific article; zbMATH DE number 2080216
• scientific article; zbMATH DE number 1738671
• Nondeterministic functions and the existence of optimal proof systems
• scientific article; zbMATH DE number 1342213
• Optimal proof systems imply complete sets for promise classes

Cites work

• scientific article; zbMATH DE number 1304339 (Why is no real title available?)
• scientific article; zbMATH DE number 1335888 (Why is no real title available?)
• Classes of representable disjoint \textsf{NP}-pairs
• Do there exist complete sets for promise classes?
• Inverting onto functions.
• Nondeterministic functions and the existence of optimal proof systems
• Optimal proof systems imply complete sets for promise classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• Tuples of disjoint \(\mathsf{NP}\)-sets

Cited in

(3)

• scientific article; zbMATH DE number 1738671 (Why is no real title available?)
• scientific article; zbMATH DE number 2080216 (Why is no real title available?)
• On \(p\)-optimal proof systems and logics for PTIME

This page was built for publication: Total nondeterministic Turing machines and a p-optimal proof system for SAT

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