Some structural properties of SAT
From MaRDI portal
Publication:1587336
DOI10.1007/BF02950407zbMath0961.68053MaRDI QIDQ1587336
Publication date: 28 May 2001
Published in: Journal of Computer Science and Technology (Search for Journal in Brave)
Cites Work
- NP-hard sets are superterse unless NP is small
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- The complexity of optimization problems
- A taxonomy of complexity classes of functions
- Some connections between bounded query classes and non-uniform complexity.
- Resource-Bounded Kolmogorov Complexity Revisited
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Structural analysis of the complexity of inverse functions
- New Collapse Consequences of NP Having Small Circuits
- Complexity-Restricted Advice Functions
- Measure, Stochasticity, and the Density of Hard Languages
- The complexity of generating and checking proofs of membership
- Polynomial-Time Membership Comparable Sets
This page was built for publication: Some structural properties of SAT
