Cover Image

Why the classes P and NP are not well-defined finitarily

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Anand, Bhupinder Singh
Format:	Preprint
Published:	2024
Subjects:	Logic 00A30, 03A05, 03B10, 03D10, 03D15, 03F25, 03F30, 68Q15, 68Q17, 68T27
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

Regainingly approximable numbers and sets
by: Hertling, Peter, et al.
Published: (2023)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

On Chaitin's Heuristic Principle and Halting Probability
by: Salehi, Saeed
Published: (2023)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

Finitely Bounded Homogeneity Turned Inside-Out
by: Rydval, Jakub
Published: (2021)

A non-speedup result for the chain-antichain principle over a weak base theory
by: Kowalik, Katarzyna W.
Published: (2025)

Computability of Initial Value Problems
by: Brattka, Vasco, et al.
Published: (2024)

Strong Kurtz Randomness and Binary Expansions of Reordered Computable Numbers
by: Hertling, Peter, et al.
Published: (2025)

Dilators and the reverse mathematics zoo
by: Freund, Anton
Published: (2024)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy
by: Sorg, Christopher
Published: (2026)

The cohesive and stable Ramsey theorems and proof size over a weak base theory
by: Kołodziejczyk, Leszek Aleksander, et al.
Published: (2026)

Solovay reducibility implies S2a-reducibility
by: Titov, Ivan
Published: (2024)

A total Solovay reducibility and totalizing of the notion of speedability
by: Merkle, Wolfgang, et al.
Published: (2024)

Choiceless Polynomial Space
by: Ferrarotti, Flavio, et al.
Published: (2024)

Complexity of deep computations via topology of function spaces
by: Dueñez, Eduardo, et al.
Published: (2026)

Robinson Splitting Theorem and $Σ_1$ Induction
by: Liu, Yong, et al.
Published: (2026)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

A Cut-Free Sequent Calculus for the Analysis of Finite-Trace Properties in Concurrent Systems
by: Fusco, Ludovico, et al.
Published: (2025)

Learning Equivalence Relations on Polish Spaces
by: Rossegger, Dino, et al.
Published: (2024)

The strength of Ramsey's theorem for $α$-large sets
by: Carlucci, Lorenzo, et al.
Published: (2026)

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index
by: Sorg, Christopher
Published: (2026)

The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)

Information vs Dimension -- an Algorithmic Perspective
by: Reimann, Jan
Published: (2024)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
by: Bannach, Max, et al.
Published: (2025)

Remarks on Primitive Regulation
by: Rosko, Milan
Published: (2026)

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
by: Kattermann, David, et al.
Published: (2025)

The finite cohesiveness principle
by: Sun, Mengzhou
Published: (2025)

Is Peirce's reduction thesis gerrymandered?
by: Koshkin, Sergiy
Published: (2024)

Largeness notions and polytime translation for $\forall Σ^0_3$-consequences of $\mathsf{RT}^2_2$
by: Houérou, Quentin Le, et al.
Published: (2026)

On the limits of comparing subset sizes within $\mathbb{N}$
by: Wenmackers, Sylvia
Published: (2024)

Maximal order types for sequences with gap condition
by: Uftring, Patrick
Published: (2025)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Induction on Dilators and Bachmann-Howard Fixed Points
by: Aguilera, Juan P., et al.
Published: (2024)

$Π^0_4$ conservation of the Ordered Variable Word theorem
by: Houérou, Quentin Le, et al.
Published: (2024)

$Π^0_4$ conservation of Ramsey's theorem for pairs
by: Houérou, Quentin Le, et al.
Published: (2024)

On inverse Goodstein sequences
by: Uftring, Patrick
Published: (2023)

The Fractal Logic of Phi-adic Recursion
by: Rosko, Milan
Published: (2025)