scientific article
From MaRDI portal
Publication:3334986
zbMath0545.68036MaRDI QIDQ3334986
Publication date: 1984
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
equivalence relationsBorel setsNP-completerecognition problemTuring reducibilitypolynomial-timeoraclesNP setsinvariant problemfirst member problemnormal form problem
Analysis of algorithms and problem complexity (68Q25) Descriptive set theory (03E15) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (8)
Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Fields of algebraic numbers computable in polynomial time. II ⋮ History and basic features of the critical-pair/completion procedure ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The shrinking property for NP and coNP ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Complexity classes of equivalence problems revisited ⋮ Searching for applicable versions of computable structures
This page was built for publication:
