Relative complexity of checking and evaluating
From MaRDI portal
Publication:1232181
DOI10.1016/0020-0190(76)90097-1zbMath0342.68028MaRDI 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
68Q25: Analysis of algorithms and problem complexity
Related Items
Restrictive Acceptance Suffices for Equivalence Problems, On sets bounded truth-table reducible to $P$-selective sets, Counting classes: Thresholds, parity, mods, and fewness, Finite-model theory -- A personal perspective, Unambiguous computations and locally definable acceptance types, On sets polynomially enumerable by iteration, Separating complexity classes with tally oracles, Turing machines with few accepting computations and low sets for PP, On polynomial time one-truth-table reducibility to a sparse set, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Polynomial-time compression, On the power of enumerative counting, Graph isomorphism is low for PP, Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory, A taxonomy of complexity classes of functions, Non-deterministic communication complexity with few witnesses, Recursion theoretic characterizations of complexity classes of counting functions, How to define a linear order on finite models, A second step towards complexity-theoretic analogs of Rice's Theorem, Characterizing the existence of one-way permutations, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, A complexity theory for feasible closure properties, Collapsing degrees via strong computation, Simultaneous strong separations of probabilistic and unambiguous complexity classes, A survey of one-way functions in complexity theory, Structure and importance of logspace-MOD class, Structural analysis of the complexity of inverse functions
