On an optimal deterministic algorithm for SAT

DOI10.1007/10703163_13MaRDI QIDQ4263798zbMATH OpenFDO

Authors Zenon Sadowski

Publication date 25 April 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10703163_13

zbMATH Keywords

optimal deterministic algorithm for SATp-optimal proof systems

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 2080216
• scientific article; zbMATH DE number 1738671
• Total nondeterministic Turing machines and a p-optimal proof system for SAT
• On optimal algorithms and optimal proof systems
• scientific article; zbMATH DE number 5999718

Cited in

(17)

• On the greedy algorithm for satisfiability
• Optimal deterministic algorithm generation
• Optimal heuristic algorithms for the image of an injective function
• Total nondeterministic Turing machines and a p-optimal proof system for SAT
• The SAT+CAS method for combinatorial search with applications to best matrices
• An enumerative algorithm for \#2SAT
• scientific article; zbMATH DE number 5914170 (Why is no real title available?)
• 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 1182571 (Why is no real title available?)
• scientific article; zbMATH DE number 2080216 (Why is no real title available?)
• scientific article; zbMATH DE number 6874827 (Why is no real title available?)
• STACS 2004
• Hard instances of algorithms and proof systems
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Nondeterministic functions and the existence of optimal proof systems

This page was built for publication: On an optimal deterministic algorithm for SAT

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