scientific article; zbMATH DE number 3594673

zbMath0382.68068MaRDI QIDQ4160434

Piotr Berman

Publication date: 1978

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (24)

Reductions among polynomial isomorphism types ⋮ A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Computation times of NP sets of different densities ⋮ Self-reducibility ⋮ Affine automata verifiers ⋮ Collapsing degrees ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ On the complexity of computing the Hausdorff distance ⋮ The maximum value problem and NP real numbers ⋮ A result relating disjunctive self-reducibility to P-immunity ⋮ On the structure of sets in NP and other complexity classes ⋮ A uniform approach to obtain diagonal sets in complexity classes ⋮ A note on sparse oracles for NP ⋮ Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ A note on P-selective sets and closeness ⋮ Classes of bounded nondeterminism ⋮ Reductions to sets of low information content ⋮ Monotonous and randomized reductions to sparse sets ⋮ Relativizing relativized computations ⋮ On self-reducibility and weak P-selectivity ⋮ Some consequences of non-uniform conditions on uniform classes ⋮ Padding, commitment and self-reducibility

This page was built for publication: