Relative complexity of checking and evaluating
From MaRDI portal
Publication:1232181
DOI10.1016/0020-0190(76)90097-1zbMath0342.68028OpenAlexW2044504659MaRDI QIDQ1232181
Publication date: 1976
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(76)90097-1
Related Items (89)
A taxonomy of complexity classes of functions ⋮ One-way permutations and self-witnessing languages ⋮ The Untold Story of $$\mathsf {SBP}$$ ⋮ A complexity theory for feasible closure properties ⋮ Collapsing degrees via strong computation ⋮ Non-deterministic communication complexity with few witnesses ⋮ A note on quadratic residuosity and UP ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ NP is as easy as detecting unique solutions ⋮ Random parallel algorithms for finding exact branchings, perfect matchings, and cycles ⋮ One-way functions and circuit complexity ⋮ On hardness of one-way functions ⋮ On helping by robust oracle machines ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ Computational tameness of classical non-causal models ⋮ Complexity classes without machines: on complete languages for UP ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ How to define a linear order on finite models ⋮ On intractability of the classUP ⋮ Tight lower bounds on the ambiguity of strong, total, associative, one-way functions ⋮ A survey of one-way functions in complexity theory ⋮ Structure and importance of logspace-MOD class ⋮ The expressive power of unique total stable model semantics ⋮ The complexity of computing the permanent ⋮ The complexity of computing minimal unidirectional covering sets ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Unambiguous computations and locally definable acceptance types ⋮ Autoreducibility, mitoticity, and immunity ⋮ On the power of unambiguity in log-space ⋮ On the power of parity polynomial time ⋮ Promise problems and access to unambiguous computation ⋮ A map of witness maps: new definitions and connections ⋮ Structural analysis of the complexity of inverse functions ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ On gamma-reducibility versus polynomial time many-one reducibility ⋮ On relativizations with restricted number of accesses to the oracle set ⋮ Robust machines accept easy sets ⋮ Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ Reductions on NP and p-selective sets ⋮ The consequences of eliminating NP solutions ⋮ On continuous one-way functions ⋮ On sets polynomially enumerable by iteration ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ Separating complexity classes with tally oracles ⋮ Immunity, simplicity, probabilistic complexity classes and relativizations ⋮ Turing machines with few accepting computations and low sets for PP ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ Implicit definability and infinitary logic in finite model theory ⋮ The complexity of identifying characteristic formulae ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ The complexity of unions of disjoint sets ⋮ Polynomial-time compression ⋮ On the power of enumerative counting ⋮ Finite-model theory -- A personal perspective ⋮ On the power of parity polynomial time ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Graph isomorphism is low for PP ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Classes of bounded nondeterminism ⋮ Lower bounds and the hardness of counting properties ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ The opacity of backbones ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Graph isomorphism is low for PP ⋮ Enumerative counting is hard ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ Characterizing the existence of one-way permutations ⋮ A low and a high hierarchy within NP ⋮ Strong nondeterministic polynomial-time reducibilities ⋮ Resource bounded immunity and simplicity ⋮ Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory ⋮ Tally NP sets and easy census functions. ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ Qualitative relativizations of complexity classes ⋮ Robust algorithms: a different approach to oracles ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Kolmogorov characterizations of complexity classes ⋮ On some natural complete operators ⋮ On total functions, existence theorems and computational complexity ⋮ On characterizing the existence of partial one-way permutations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- General context-free recognition in less than cubic time
- Proving simultaneous positivity of linear forms
- On the computational power of pushdown automata
- Optimization of LR(k) parsers
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On the Computational Complexity of Algorithms
- Minimum partition of a matroid into independent subsets
- The complexity of theorem-proving procedures
This page was built for publication: Relative complexity of checking and evaluating
