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

DOI10.1007/978-3-319-58741-7_34zbMATH Open1489.68095OpenAlexW2613545522MaRDI QIDQ2011675FDOQ2011675

Authors: Zenon Sadowski 

Publication date: 4 August 2017

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

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

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)

Cites Work

• The relative efficiency of propositional 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
• Inverting onto functions.
• Title not available (Why is that?)
• Nondeterministic functions and the existence of optimal proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Tuples of disjoint \(\mathsf{NP}\)-sets
• Title not available (Why is that?)
• Do there exist complete sets for promise classes?

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)