All Questions
Tagged with computer-science np
14 questions
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
4
votes
1
answer
362
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 1,207
1
vote
1
answer
182
views
Boolean function : approximation by a linear function
Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...
- 4,074
0
votes
1
answer
210
views
Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]
Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
- 1
1
vote
1
answer
347
views
Finding a subgraph of cliques with the minimum total sum weight
Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...
- 113
7
votes
3
answers
1k
views
How slow are direct solutions of NP-complete problems on computers?
Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. ...
- 171
5
votes
0
answers
139
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} \...
- 1,368
18
votes
7
answers
3k
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 ...
- 1,368
3
votes
1
answer
1k
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 ...
4
votes
1
answer
248
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 deterministic TM $M$ accepting
$$
\text{coBHP}=\{\...
9
votes
3
answers
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 ...
- 2,895
22
votes
3
answers
6k
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 ...
- 4,729
14
votes
2
answers
4k
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 ...
- 597
1
vote
3
answers
1k
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?
- 213