Computing functions with parallel queries to NP
From MaRDI portal
Recommendations
- The parallel complexity of function approximation
- Functions computable with nonadaptive queries to NP
- scientific article; zbMATH DE number 54587
- On parallel complexity of analytic functions
- scientific article; zbMATH DE number 1305047
- scientific article; zbMATH DE number 4068238
- scientific article; zbMATH DE number 3988712
- Parallel computation with threshold functions
- scientific article; zbMATH DE number 1163093
Cites work
- scientific article; zbMATH DE number 176523 (Why is no real title available?)
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- scientific article; zbMATH DE number 512846 (Why is no real title available?)
- scientific article; zbMATH DE number 1414313 (Why is no real title available?)
- A comparison of polynomial time reducibilities
- A note on the graph isomorphism counting problem
- A taxonomy of complexity classes of functions
- Approximation algorithms for combinatorial problems
- Bounded Query Classes
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- Classes of bounded nondeterminism
- Constant Depth Reducibility
- Enumerative counting is hard
- Functions computable with nonadaptive queries to NP
- NP is as easy as detecting unique solutions
- On counting and approximation
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- On the Decomposability of $NC$ and $AC$
- On the unique satisfiability problem
- Positive Relativizations of Complexity Classes
- Relativization of questions about log space computability
- Self-witnessing polynomial-time complexity and prime factorization
- The complexity of computing the permanent
- The complexity of optimization problems
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
Cited in
(25)- On adaptive DLOGTIME and POLYLOGTIME reductions
- On sets bounded truth-table reducible to $P$-selective sets
- The computational complexity of ideal semantics
- scientific article; zbMATH DE number 1254029 (Why is no real title available?)
- Expressive probabilistic description logics
- Combining experts' causal judgments
- Sparse sets, approximable sets, and parallel queries to NP
- Graph Isomorphism is in SPP
- Complexity of counting the optimal solutions
- Semiring reasoning frameworks in AI and their computational complexity
- scientific article; zbMATH DE number 1304344 (Why is no real title available?)
- Complexity results for explanations in the structural-model approach
- On the complexity of data disjunctions.
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- scientific article; zbMATH DE number 176523 (Why is no real title available?)
- The complexity class θp2: Recent results and applications in AI and modal logic
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- Weighted argument systems: basic definitions, algorithms, and complexity results
- Probabilistic logic under coherence: complexity and algorithms
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- Combining answer set programming with description logics for the semantic web
- Resource-bounded Kolmogorov complexity revisited
- Monotonous and randomized reductions to sparse sets
- ANALYSIS OF QUANTUM FUNCTIONS
- Complexity of Counting the Optimal Solutions
This page was built for publication: Computing functions with parallel queries to NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673784)
