New answers tagged np
4
Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating:
Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; ...
1
Yes in case of 3-sum problem they are equivalent. Let $P$ be the version where the three numbers have to be distinct and $P'$ the version where you can use the same number multiple times. The reduction $P'$ to $P$ is by solving the cases with overlapping in preprocessing (since both overlapping cases can be done in almost linear time).
The other direction ...
1
For any instance of a problem, take the instance itself as the certificate. Linear size, verifiable in polynomial time for problems in P, not known for problems in NP.
0
Every NEXPTIME complete language has a certificate of length 0 that can be checked in time $2^{2^{n^{O(1)}}}$, but does not have polynomial length certificate that can be checked in polynomial time.
1
Your understanding is correct, but the takeaway here is that assuming the contradictions implies that anything can be true. Perhaps reading up on some logic rules might help, the important rule here is that $\bot$ (false) implies everything. Here is a little proof of the problem just for fun:
We know that both 3-SAT and Set Cover are NP-Complete problems.
...
2
You are confusing NP and NP-hard in a couple places. For example, let $A$ be the problem of deciding ATL*, which is 2EXPTIME-complete. $A$ is NP-hard and polynomial-time many-one reduces to its complement, but is neither in NP nor in co-NP by the time hierarchy theorem.
Recall that an NP-complete problem is one that is in NP and is NP-hard. For every NP-...
Top 50 recent answers are included
