New answers tagged complexity-classes
0
To give you an idea of the “why”: A yes/no problem is an NP if you can prove the answer is “yes” by making an incredibly lucky guess, plus some moderate amount of work.
For example: Can I make a tour connecting the capitals of the 48 main states of the USA in at most 10,000 miles? If the answer is “yes” then I make a lucky guess in which order to visit the ...
2
In regards to the relationship between discrete logarithm and factoring, it seems worth mentioning that both problems are special cases of the Hidden Subgroup Problem. Shor's Algorithm, under the covers, is really solving this problem. Here are some references: factorization, discrete log.
The last link also mentions how integer factorization can tecnically ...
1
It is actually finding the number that is NP-complete. The (decision) problem is formally stated as follows:
Vertex cover. Given a graph $G = (V, E)$ and an integer $k$, does there exist a set of at most $k$ vertices $C \subseteq V$ such that every edge has at least one endpoint in $C$?
As you can see, this is precisely your $\tau(G)$.
The other problem is ...
1
Suppose there is an algorithm $A(G,c)$ which runs in time $T(n)$, where $n$ is the number of vertices in $G$, as long as $c$ is the vertex cover number.
Given a graph $G$, run $A(G,0),\ldots,A(G,n)$ in parallel, for $T(n)$ time each. Some of the copies will terminate within $T(n)$, outputting a set. Out of all such outputs which are vertex covers, choose the ...
Top 50 recent answers are included
