# Tag Info

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
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
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
Accepted

### Are there any links between descriptive set theory and computational complexity theory?

Sure! Here's a whole book about it.
• 1,765
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
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