Pages that link to "Item:Q3771612"
From MaRDI portal
The following pages link to A complexity theory based on Boolean algebra (Q3771612):
Displaying 35 items.
- Complete problems for monotone NP (Q673092) (← links)
- Methods for proving completeness via logical reductions (Q685391) (← links)
- Hypertree decompositions and tractable queries (Q696962) (← links)
- A measure in which Boolean negation is exponentially powerful (Q790083) (← links)
- Weighted hypertree decompositions and optimal query plans (Q878759) (← links)
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree (Q910223) (← links)
- Polynomial size \(\Omega\)-branching programs and their computational power (Q918199) (← links)
- Threshold functions and bounded depth monotone circuits (Q1088970) (← links)
- The monotone circuit complexity of Boolean functions (Q1094870) (← links)
- Feasible arithmetic computations: Valiant's hypothesis (Q1114391) (← links)
- There are no p-complete families of symmetric Boolean functions (Q1114662) (← links)
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696) (← links)
- On monotone simulations on nonmonotone networks (Q1121853) (← links)
- Properties that characterize LOGCFL (Q1176109) (← links)
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\) (Q1178711) (← links)
- Nonuniform complexity and the randomness of certain complete languages (Q1184988) (← links)
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems (Q1185244) (← links)
- Using the Hamiltonian path operator to capture NP (Q1198664) (← links)
- Completeness and non-completeness results with respect to read-once projections (Q1271310) (← links)
- Complexity models for incremental computation (Q1331947) (← links)
- A reducibility concept for problems defined in terms of ordered binary decision diagrams (Q1364133) (← links)
- Gap-languages and log-time complexity classes (Q1389651) (← links)
- On the algebraic complexity of some families of coloured Tutte polynomials (Q1433009) (← links)
- Expressiveness of matchgates. (Q1853537) (← links)
- Threshold circuits of bounded depth (Q2366275) (← links)
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits (Q2817792) (← links)
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas (Q2968156) (← links)
- A theory of boolean integration (Q3481649) (← links)
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines (Q4020492) (← links)
- Some results on uniform arithmetic circuit complexity (Q4285623) (← links)
- Lower bounds for the majority communication complexity of various graph accessibility problems (Q4717056) (← links)
- Uniform Constraint Satisfaction Problems and Database Theory (Q5504703) (← links)
- On pseudorandomness and resource-bounded measure (Q5941070) (← links)
- Dot operators (Q5958134) (← links)
- Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024 (Q6671618) (← links)
