5
votes
0answers
106 views

Are there sampNP-intermediate problems?

This questions is approximately cross-posted from theoretical computer science stackexchange Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} ...
12
votes
6answers
1k views

SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
2
votes
1answer
454 views

#P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
1
vote
0answers
167 views

Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed? More precisely, suppose that for any $M$ accepting $$ \text{coBHP}=\{\langle ...
8
votes
3answers
1k views

Non-existence of algorithm converting NP algorithm to P algorithm?

[Edit: in the light of Nate Eldredge's answer below I rephrase the question] P=NP is equivalent to the existence of a map of the following form: Input: a polynomial-time non-deterministic Turing ...
18
votes
3answers
2k views

Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
6
votes
2answers
1k views

Best-case Running-time to solve an NP-Complete problem

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
0
votes
3answers
419 views

How can one characterize NP^SAT?

Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?