Polynomial-time axioms of choice and polynomial-time cardinality
From MaRDI portal
Publication:6109071
DOI10.1007/S00224-023-10118-YarXiv2301.07123OpenAlexW4376609569MaRDI QIDQ6109071
Publication date: 26 July 2023
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2301.07123
axiom of choicecardinalitystructural complexityp-isomorphismfunction complexityfunction invertibilitystructural properties of languages
Theory of computing (68Qxx) Mathematical logic and foundations (03-XX) Computability and recursion theory (03Dxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity classes of equivalence problems revisited
- Autoreducibility, mitoticity, and immunity
- Complexity-theoretic algebra. II: Boolean algebras
- The complexity of unions of disjoint sets
- On some natural complete operators
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Realizability and recursive set theory
- Collapsing degrees
- Some observations on NP real numbers and P-selective sets
- Reductions on NP and p-selective sets
- On truth-table reducibility to SAT
- On sets polynomially enumerable by iteration
- Polynomial-time compression
- A second step toward the polynomial hierarchy
- A taxonomy of complexity classes of functions
- Scalability and the isomorphism problem
- Inverting onto functions.
- Computable structures and the hyperarithmetical hierarchy
- The counting complexity of group-definable languages
- \(p\)-Selective sets and reducing search to decision vs. self-reducibility
- Reductions between disjoint NP-pairs
- Introduction to Autoreducibility and Mitoticity
- Generalized Effective Reducibility
- Category and Measure in Complexity Classes
- Splitting NP-Complete Sets
- Complexity Measures for Public-Key Cryptosystems
- Natural Self-Reducible Sets
- Completeness, Approximation and Density
- Compression and Ranking
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Polynomial Time Enumeration Reducibility
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- The isomorphism conjecture fails relative to a random oracle
- Disjoint NP-Pairs
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Computable Structure Theory
- Finite axioms of choice
- Every polynomial-time 1-degree collapses if and only if P = PSPACE
- The recursive equivalence type of a class of sets
- Theory and Applications of Models of Computation
- Axiom of choice
- Theory of semi-feasible algorithms
This page was built for publication: Polynomial-time axioms of choice and polynomial-time cardinality
