Resource bounded immunity and simplicity (Q2576870): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2005.03.055
+Normal rank
@@ Property / OpenAlex ID @@
+W1974993202
@@ Property / OpenAlex ID: W1974993202 / rank @@
+Normal rank
@@ Property / cites work @@
+Diagonalizations over polynomial time computable sets
+Normal rank
@@ Property / cites work @@
+Q4734760
@@ Property / cites work: Q4734760 / rank @@
+Normal rank
@@ Property / cites work @@
+Simplicity, Relativizations and Nondeterminism
@@ Property / cites work: Simplicity, Relativizations and Nondeterminism / rank @@
+Normal rank
@@ Property / cites work @@
+Q3996675
@@ Property / cites work: Q3996675 / rank @@
+Normal rank
@@ Property / cites work @@
+Bi-immune sets for complexity classes
@@ Property / cites work: Bi-immune sets for complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy I: Structural Properties
@@ Property / cites work: The Boolean Hierarchy I: Structural Properties / rank @@
+Normal rank
@@ Property / cites work @@
+Q4942157
@@ Property / cites work: Q4942157 / rank @@
+Normal rank
@@ Property / cites work @@
+Generic separations
@@ Property / cites work: Generic separations / rank @@
+Normal rank
@@ Property / cites work @@
+TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3801071
@@ Property / cites work: Q3801071 / rank @@
+Normal rank
@@ Property / cites work @@
+Defying upward and downward separation
@@ Property / cites work: Defying upward and downward separation / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Solutions Uniquely Collapses the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Strong self-reducibility precludes strong immunity
+Normal rank
@@ Property / cites work @@
+Classes bounded by incomplete sets
@@ Property / cites work: Classes bounded by incomplete sets / rank @@
+Normal rank
@@ Property / cites work @@
+On simple and creative sets in NP
@@ Property / cites work: On simple and creative sets in NP / rank @@
+Normal rank
@@ Property / cites work @@
+Oracle-dependent properties of the lattice of NP sets
+Normal rank
@@ Property / cites work @@
+Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
+Normal rank
@@ Property / cites work @@
+Nonlevelable sets and immune sets in the accepting density hierarchy inNP
+Normal rank
@@ Property / cites work @@
+Completeness, Approximation and Density
@@ Property / cites work: Completeness, Approximation and Density / rank @@
+Normal rank
@@ Property / cites work @@
+On the Structure of Polynomial Time Reducibility
@@ Property / cites work: On the Structure of Polynomial Time Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+On Reducibility to Complex or Sparse Sets
@@ Property / cites work: On Reducibility to Complex or Sparse Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3232283
@@ Property / cites work: Q3232283 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on balanced immunity
@@ Property / cites work: A note on balanced immunity / rank @@
+Normal rank
@@ Property / cites work @@
+A classification of complexity core lattices
@@ Property / cites work: A classification of complexity core lattices / rank @@
+Normal rank
@@ Property / cites work @@
+Instance complexity
@@ Property / cites work: Instance complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Approximations and Polynomially Levelable Sets
+Normal rank
@@ Property / cites work @@
+Recursively enumerable sets of positive integers and their decision problems
+Normal rank
@@ Property / cites work @@
+Immunity and Simplicity for Exact Counting and Other Counting Classes
+Normal rank
@@ Property / cites work @@
+Q3770515
@@ Property / cites work: Q3770515 / rank @@
+Normal rank
@@ Property / cites work @@
+A low and a high hierarchy within NP
@@ Property / cites work: A low and a high hierarchy within NP / rank @@
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+A taxonomy of complexity classes of functions
@@ Property / cites work: A taxonomy of complexity classes of functions / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+A second step toward the strong polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Simplicity, immunity, relativizations and nondeterminism
+Normal rank
@@ Property / cites work @@
+[Russian Text Ignored]
@@ Property / cites work: [Russian Text Ignored] / rank @@
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank
@@ Property / cites work @@
+Complete sets and the polynomial-time hierarchy
@@ Property / cites work: Complete sets and the polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Structural properties for feasibly computable classes of type two
+Normal rank