mihaild · HackerTrans

mihaild

no profile record

comments

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 be colored in 3 colors even after removing eps part of edges" with large polynomials (IIRC, we got something like O(n^{2^40000}) when tried to find degree explicitly).

mihaild

9 anni fadiscuss

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

mihaild

9 anni fadiscuss

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. If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.

mihaild

9 anni fadiscuss

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.

mihaild

9 anni fadiscuss

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 NP, for example)

mihaild

9 anni fadiscuss

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't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.

mihaild

9 anni fadiscuss

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 solutions for known-solvable instances)

mihaild

9 anni fadiscuss

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.