Cover Image

A Note On The Natural Range Of Unambiguous-SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Pay, Tayfun
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity F.1.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Realizable Circuit Complexity: Embedding Computation in Space-Time
by: Prada, Benjamin, et al.
Published: (2025)

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, et al.
Published: (2025)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
by: Iturralde, Paúl Risco
Published: (2025)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

On the Computation of 2-Dimensional Recurrence Equations
by: Natale, Giuseppe
Published: (2024)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

Eulerian orientations and Hadamard codes: A novel connection via counting
by: Shao, Shuai, et al.
Published: (2024)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
by: Fan, Austen, et al.
Published: (2026)

Small Shadow Partitions
by: Kopparty, Swastik, et al.
Published: (2024)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

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

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Classifying extrema using intervals
by: Gutowski, Marek W.
Published: (2006)

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

SAT problem and Limit of Solomonoff's inductive reasoning theory
by: Pan, Feng
Published: (2025)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

On the Decidability of Verification under Release/Acquire
by: Conrado, Giovanna Kobus, et al.
Published: (2026)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
by: Chen, Yanlin, et al.
Published: (2023)

Condensing and Extracting Against Online Adversaries
by: Chattopadhyay, Eshan, et al.
Published: (2024)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

Simple Stochastic Stopping Games: A Generator and Benchmark Library
by: Rudich, Avi, et al.
Published: (2024)

A point to set principle for finite-state dimension
by: Mayordomo, Elvira
Published: (2022)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
by: Cheval, Vincent, et al.
Published: (2025)

On the location of zeros of a quaternion polynomial
by: Rather, N. A., et al.
Published: (2025)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
by: Bajaj, Divya, et al.
Published: (2026)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework
by: Luberisse, Joshua
Published: (2025)

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

L is different from NP
by: Montoya, J. Andres
Published: (2024)