mihaild

4 ms·

1.
by mihaild 9y ago
For example, there is 0.8776-approximation that runs in about O(n^{10^100}) https://arxiv.org/abs/1205.0458v2 There are also a lot of graph problems like "distinguish 3-colorable graph from graph that can't b
2.
by mihaild 9y ago
I don't. (it's always hard to find reference for easy problems)
3.
by mihaild 9y ago
Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ... After program stops, we check if its output is our witness.
4.
by mihaild 9y ago
For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.
5.
by mihaild 9y ago
Decision version of TSP is NP-complete. Optimization version is Cook-reducible to decision version of TSP. And it problem is Cook-reducible to P-problem, then the problem is itself in P. (note that it's not true if you replace P with N
6.
by mihaild 9y ago
Epsilon isn't a problem, as TSP is NP-complete even for integer weights. Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle). I don'
7.
by mihaild 9y ago
There is Universal Search algorithm. If P=NP, it finds a solution for solvable 3-SAT in polynomial time. (still not solving 3-SAT itself in case we will not be able to determine running time, but in cryptography AFAIK we usually need soluti
8.
by mihaild 9y ago
First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.