Pages that link to "Item:Q908700"
From MaRDI portal
The following pages link to \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP (Q908700):
Displaying 22 items.
- Belief revision within fragments of propositional logic (Q386044) (← links)
- Kolmogorov characterizations of complexity classes (Q804291) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- On the complexity of propositional knowledge base revision, updates, and counterfactuals (Q1199919) (← links)
- On reductions of NP sets to sparse sets (Q1329162) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Some structural properties of SAT (Q1587336) (← links)
- Computing properties of stable configurations of thermodynamic binding networks (Q2315010) (← links)
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete (Q2367539) (← links)
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison (Q2404077) (← links)
- The complexity of comparing optimal solutions (Q2671811) (← links)
- Do there exist complete sets for promise classes? (Q3107337) (← links)
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP (Q3374757) (← links)
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP (Q4571954) (← links)
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ (Q4717047) (← links)
- Monotonous and randomized reductions to sparse sets (Q4717050) (← links)
- On computing Boolean connectives of characteristic functions (Q4835862) (← links)
- Upper bounds for the complexity of sparse and tally descriptions (Q4864446) (← links)
- The complexity class θp2: Recent results and applications in AI and modal logic (Q5055917) (← links)
- Reductions to sets of low information content (Q5204315) (← links)
- Weak cardinality theorems (Q5718691) (← links)
- On pseudorandomness and resource-bounded measure (Q5941070) (← links)
