Short propositional formulas represent nondeterministic computations

DOI10.1016/0020-0190(88)90152-4zbMath0633.68034OpenAlexW2117427692MaRDI QIDQ1096390

Stephen A. Cook

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90152-4

zbMATH Keywords

NP-completesatisfiabilityconjunctive normal formnondeterministic Turing machine

Mathematics Subject Classification ID

Related Items (14)

Local Reductions ⋮ Local reduction ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Smoothing the Gap Between NP and ER ⋮ Robust simulations and significant separations ⋮ Unnamed Item ⋮ On membership comparable sets ⋮ Power indices and easier hard problems ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ On the communication complexity of zero-knowledge proofs ⋮ Sorting, linear time and the satisfiability problem ⋮ On O(Tlog T) reduction from RAM computations to satisfiability ⋮ Time-space tradeoffs for satisfiability ⋮ A time lower bound for satisfiability

Cites Work

• Satisfiability Is Quasilinear Complete in NQL
• Relations Among Complexity Measures
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item

This page was built for publication: Short propositional formulas represent nondeterministic computations