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
- 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
- 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?)
- 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
- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
Cited in
(27)- The computational complexity of ideal semantics
- Functions computable with nonadaptive queries to NP
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- On the complexity of data disjunctions.
- Combining experts' causal judgments
- Expressive probabilistic description logics
- Combining answer set programming with description logics for the semantic web
- Graph Isomorphism is in SPP
- Sparse sets, approximable sets, and parallel queries to NP
- Complexity of Counting the Optimal Solutions
- scientific article; zbMATH DE number 176523 (Why is no real title available?)
- scientific article; zbMATH DE number 1254029 (Why is no real title available?)
- scientific article; zbMATH DE number 1304344 (Why is no real title available?)
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- On sets bounded truth-table reducible to P-selective sets
- Monotonous and randomized reductions to sparse sets
- Resource-bounded Kolmogorov complexity revisited
- The complexity class θp2: Recent results and applications in AI and modal logic
- Weighted argument systems: basic definitions, algorithms, and complexity results
- ANALYSIS OF QUANTUM FUNCTIONS
- Semiring reasoning frameworks in AI and their computational complexity
- On adaptive DLOGTIME and POLYLOGTIME reductions
- A rule-based modal framework for causal reasoning
- Complexity results for explanations in the structural-model approach
- Probabilistic logic under coherence: complexity and algorithms
- 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)
