Relative complexity of checking and evaluating

Cites work

scientific article; zbMATH DE number 3141365 (Why is no real title available?)
scientific article; zbMATH DE number 3571502 (Why is no real title available?)
scientific article; zbMATH DE number 3303654 (Why is no real title available?)
scientific article; zbMATH DE number 3311755 (Why is no real title available?)
General context-free recognition in less than cubic time
Minimum partition of a matroid into independent subsets
On the Computational Complexity of Algorithms
On the computational power of pushdown automata
Optimization of LR(k) parsers
Proving simultaneous positivity of linear forms
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
The complexity of theorem-proving procedures

Cited in

(91)

On characterizing the existence of partial one-way permutations
On polynomial time one-truth-table reducibility to a sparse set
One-way functions and circuit complexity
The complexity of identifying characteristic formulae
Optimal series-parallel trade-offs for reducing a function to its own graph
Reductions on NP and p-selective sets
Robust machines accept easy sets
Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
Structural analysis of the complexity of inverse functions
A note on quadratic residuosity and UP
Immunity, simplicity, probabilistic complexity classes and relativizations
Separating complexity classes with tally oracles
A survey of one-way functions in complexity theory
Implicit definability and infinitary logic in finite model theory (extended abstract)
The complexity of computing the permanent
Generalized implicit definitions on finite structures
On continuous one-way functions
Nondeterministic functions and the existence of optimal proof systems
Promise problems and access to unambiguous computation
Finite-model theory -- A personal perspective
Structure and importance of logspace-MOD class
Enumerative counting is hard
One-way permutations and self-witnessing languages
Lower bounds and the hardness of counting properties
Tally NP sets and easy census functions.
On gamma-reducibility versus polynomial time many-one reducibility
Approximation of boolean functions by combinatorial rectangles
On intractability of the classUP
Polynomial-time compression
Finding strongly popular $b$-matchings in bipartite graphs
Qualitative relativizations of complexity classes
A taxonomy of complexity classes of functions
Resource bounded immunity and simplicity
Recursion theoretic characterizations of complexity classes of counting functions
Turing machines with few accepting computations and low sets for PP
Classes of bounded nondeterminism
Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
Immunity and simplicity in relativizations of probabilistic complexity classes
A second step towards complexity-theoretic analogs of Rice's Theorem
Unambiguous computations and locally definable acceptance types
Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
Kolmogorov characterizations of complexity classes
Polynomial-time 1-Turing reductions from $\#$PH to $\#$P
The robustness of LWPP and WPP, with an application to graph reconstruction
Autoreducibility, mitoticity, and immunity
Robust algorithms: a different approach to oracles
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
Collapsing degrees via strong computation
On sets bounded truth-table reducible to $P$-selective sets
On helping by robust oracle machines
Complexity classes without machines: on complete languages for UP
On the relative complexity of hard problems for complexity classes without complete problems
Counting classes: Thresholds, parity, mods, and fewness
The consequences of eliminating NP solutions
A map of witness maps: new definitions and connections
On total functions, existence theorems and computational complexity
On some natural complete operators
Program size complexity of correction grammars in the Ershov hierarchy
NP is as easy as detecting unique solutions
On hardness of one-way functions
Finding strongly popular $b$-matchings in bipartite graphs
Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
Quantum and classical complexity classes: Separations, collapses, and closure properties
On relativizations with restricted number of accesses to the oracle set
Strong nondeterministic polynomial-time reducibilities
On sets polynomially enumerable by iteration
The opacity of backbones
Fault-tolerance and complexity (extended abstract)
Intersection suffices for Boolean hierarchy equivalence
On the power of counting the total number of computation paths of NPTMs
The Untold Story of $$\mathsf {SBP}$$
The expressive power of unique total stable model semantics
Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
On the power of unambiguity in log-space
Computational tameness of classical non-causal models
On the power of enumerative counting
How to define a linear order on finite models
A low and a high hierarchy within NP
The complexity of unions of disjoint sets
One-way functions and the nonisomorphism of NP-complete sets
Graph isomorphism is low for PP
Non-deterministic communication complexity with few witnesses
Graph isomorphism is low for PP
On the power of parity polynomial time
On the power of parity polynomial time
A complexity theory for feasible closure properties
Simultaneous strong separations of probabilistic and unambiguous complexity classes
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Restrictive Acceptance Suffices for Equivalence Problems
Power of counting by nonuniform families of polynomial-size finite automata
Characterizing the existence of one-way permutations

This page was built for publication: Relative complexity of checking and evaluating

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1232181)