Viewing profile — mihaild

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 g…

I don't. (it's always hard to find reference for easy problems)

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; ...…

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 u…

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…

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 edge…

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 ru…

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 t…