3
votes
Accepted
Does it have to be $P = NP$ or $P \neq NP$?
I think the question relies on a misunderstanding of what “undecidable” means (and hopefully my understanding is not too naive here).
First, undecidability is always defined with respect to (a ...
- 35.9k
2
votes
Accepted
If SubsetSum can be solved in pseudopolynomial time, can we karp reduce SAT/3SAT to it and solve in pseudopolynomial time?
There's no difference between SAT and 3-SAT here. The crux is that encoding numbers in unary doesn't change the input encoding of SAT or 3-SAT since the inputs aren't numerical, so there's no ...
- 61.1k
2
votes
Accepted
Question about the example correctness of polynomial time reducibility
In the context of reduction functions, the implied domain (and codomain) is usually $\Sigma^*$. Assuming that $\Sigma = \{0, 1\}$ (i.e. assuming that we're not dealing with some larger alphabet that ...
- 2,765
2
votes
Accepted
Are there any links between descriptive set theory and computational complexity theory?
Sure! Here's a whole book about it.
- 1,765
2
votes
Accepted
Question about proving Karp Reduction Transitive
I don't understand what you're saying in the last paragraph, so let me just explain the solution in more detail.
What they're saying is that the output size $|f(x)|$ of a poly-time function $f$ scales ...
- 61.1k
2
votes
Accepted
A Steiner tree-like problem where cycles are allowed
You don't state it directly and unambiguously, but I suppose that you want to maximize
$$\sum_{i \in I} p_i - \epsilon \sum_{e \in E} f(e),$$
where $\{\,v'_i\quad\forall i \in I\,\} \subseteq V'$ is ...
- 7,091
1
vote
Accepted
Does every permutation composition puzzle (like the Rubik's Cube) have a practical solution algorithm?
Certainly not in a cost only dependant on the size of $R$ -- every $S_n$ can be generated by two elements.
What one can prove (Keywords: Schreier-Sims algorithm, Stabilizer Chain) is that there is a ...
- 19k
Only top scored, non community-wiki answers of a minimum length are eligible