article

On truth-table reducibility to SAT

Authors:

Samuel R. Buss,

Louise HayAuthors Info & Claims

Information and Computation, Volume 91, Issue 1

Pages 86 - 102

https://doi.org/10.1016/0890-5401(91)90075-D

Published: 01 March 1991 Publication History

Abstract

No abstract available.

Cited By

View all

Bernreiter MMaly JNardi OWoltran SDastani MSichman JAlechina NDignum V(2024)Combining Voting and Abstract Argumentation to Understand Online DiscussionsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662864(170-179)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662864
Cima GConsole MLenzerini MPoggi AWilliams BChen YNeville J(2023)Epistemic disjunctive datalog for querying knowledge basesProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25773(6280-6288)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25773
Liberatore P(2023)Mixed Iterated Revisions: Rationale, Algorithms, and ComplexityACM Transactions on Computational Logic10.1145/358307124:3(1-49)Online publication date: 10-May-2023
https://dl.acm.org/doi/10.1145/3583071
Show More Cited By

Index Terms

On truth-table reducibility to SAT
1. Theory of computation

Recommendations

Weak Mitoticity of Bounded Disjunctive and Conjunctive Truth-Table Autoreducible Sets
Computing and Combinatorics
Abstract
Glaßer et al. (SIAMJCOMP 2008 and TCS 2009 (The two papers have slightly different sets of authors)) proved existence of two sparse sets A and B in EXP, where A is 3-tt (truth-table) polynomial-time autoreducible but not weakly polynomial-time ...
Deterministic and Randomized Bounded Truth-table Reductions ofP, NL, and L to Sparse Sets
The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in Dist NP under the hypothesis that P NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information and Computation Volume 91, Issue 1

March 1991

154 pages

ISSN:0890-5401

Editor:
Albert R. Meyer
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 1991

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bernreiter MMaly JNardi OWoltran SDastani MSichman JAlechina NDignum V(2024)Combining Voting and Abstract Argumentation to Understand Online DiscussionsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662864(170-179)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662864
Cima GConsole MLenzerini MPoggi AWilliams BChen YNeville J(2023)Epistemic disjunctive datalog for querying knowledge basesProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25773(6280-6288)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25773
Liberatore P(2023)Mixed Iterated Revisions: Rationale, Algorithms, and ComplexityACM Transactions on Computational Logic10.1145/358307124:3(1-49)Online publication date: 10-May-2023
https://dl.acm.org/doi/10.1145/3583071
Grochow J(2023)Polynomial-Time Axioms of Choice and Polynomial-Time CardinalityTheory of Computing Systems10.1007/s00224-023-10118-y67:3(627-669)Online publication date: 15-May-2023
https://dl.acm.org/doi/10.1007/s00224-023-10118-y
Alviano MGiordano LTheseider Dupré D(2023)Complexity and Scalability of Defeasible Reasoning with Typicality in Many-Valued Weighted Knowledge BasesLogics in Artificial Intelligence10.1007/978-3-031-43619-2_33(481-497)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43619-2_33
Zhuk DMartin B(2022)QCSP Monsters and the Demise of the Chen ConjectureJournal of the ACM10.1145/356382069:5(1-44)Online publication date: 28-Oct-2022
https://dl.acm.org/doi/10.1145/3563820
Modanese A(2022)Complexity-theoretic aspects of expanding cellular automataNatural Computing: an international journal10.1007/s11047-020-09814-221:1(53-65)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11047-020-09814-2
Cima GCroce FLenzerini MDemartini GZuccon GCulpepper JHuang ZTong H(2021)Query Definability and Its Approximations in Ontology-based Data ManagementProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482466(271-280)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482466
Jeřábek E(2021)On the Complexity of the Clone Membership ProblemTheory of Computing Systems10.1007/s00224-020-10016-765:5(839-868)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00224-020-10016-7
Zhuk DMartin BMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)QCSP monsters and the demise of the chen conjectureProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384232(91-104)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384232
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Weak Mitoticity of Bounded Disjunctive and Conjunctive Truth-Table Autoreducible Sets

Deterministic and Randomized Bounded Truth-table Reductions ofP, NL, and L to Sparse Sets

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations