Pages that link to "Item:Q1090455"
From MaRDI portal
The following pages link to The complexity of combinatorial problems with succinct input representation (Q1090455):
Displayed 50 items.
- Languages represented by Boolean formulas (Q290253) (← links)
- Dependence logic with a majority quantifier (Q302214) (← links)
- Most probable explanations in Bayesian networks: complexity and tractability (Q433524) (← links)
- Interpolation in Valiant's theory (Q451113) (← links)
- The consequences of eliminating NP solutions (Q458458) (← links)
- Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
- Extensions of MSO and the monadic counting hierarchy (Q617710) (← links)
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) (← links)
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory (Q685716) (← links)
- Lower bounds and the hardness of counting properties (Q703531) (← links)
- Probabilistic polynomial time is closed under parity reductions (Q751270) (← links)
- An oracle separating \(\oplus P\) from \(PP^{PH}\) (Q751272) (← links)
- Semidefinite programming and arithmetic circuit evaluation (Q943844) (← links)
- Efficient verification of Tunnell's criterion (Q957686) (← links)
- On the autoreducibility of functions (Q970103) (← links)
- Linear connectivity problems in directed hypergraphs (Q1029330) (← links)
- Some observations on the connection between counting and recursion (Q1098837) (← links)
- Parallel computation with threshold functions (Q1107324) (← links)
- More complicated questions about maxima and minima, and some closures of NP (Q1107524) (← links)
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) (Q1118407) (← links)
- Unambiguous computations and locally definable acceptance types (Q1127545) (← links)
- On matroids and hierarchical graphs (Q1178207) (← links)
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems (Q1185244) (← links)
- Restricted relativizations of probabilistic polynomial time (Q1186606) (← links)
- Turing machines with few accepting computations and low sets for PP (Q1190987) (← links)
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P (Q1193633) (← links)
- Generalizations of Opt P to the polynomial hierarchy (Q1193867) (← links)
- A note on the permanent value problem (Q1198001) (← links)
- On the power of enumerative counting (Q1199550) (← links)
- A uniform approach to define complexity classes (Q1200807) (← links)
- On the closure of certain function classes under integer division by polynomially-bounded functions (Q1208441) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Graph isomorphism is low for PP (Q1210331) (← links)
- Succinct representation, leaf languages, and projection reductions (Q1271623) (← links)
- Succinctness as a source of complexity in logical formalisms (Q1302307) (← links)
- Gap-definable counting classes (Q1318473) (← links)
- A note on SpanP functions (Q1328756) (← links)
- Simple characterizations of \(P(\# P)\) and complete problems (Q1333395) (← links)
- On closure properties of GapP (Q1337146) (← links)
- Universally serializable computation (Q1384538) (← links)
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits (Q1567407) (← links)
- The complexity of Bayesian networks specified by propositional and relational languages (Q1711881) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- Complexity results for structure-based causality. (Q1852862) (← links)
- Nonerasing, counting, and majority over the linear time hierarchy (Q1854524) (← links)
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing (Q1941704) (← links)
- The robustness of LWPP and WPP, with an application to graph reconstruction (Q2027204) (← links)
- On measure quantifiers in first-order arithmetic (Q2117748) (← links)
- Explainable AI using MAP-independence (Q2146024) (← links)
- The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference (Q2206456) (← links)