Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

This is a (hopefully) sharper version of a question that I asked previously.

Which of these algorithms is believed to have a longer asymptotic runtime?

  1. The optimal algorithm guaranteed to solve some NP-complete problem using a standard Turing machine.
  2. The optimal algorithm guaranteed to solve the problem described by Raz and Tal using a Turing machine with access to the oracle described in their paper. (This is the oracle $ O$ that achieves the oracle separation $ \mathrm{BQP}^O \nsubseteq \mathrm{PH}^O$ .)

(I understand that this is somewhat of an “apples-to-orange” comparison because the two Turing machines have different capabilities, but you can still compare the algorithm runtimes.)

Figure 3 of this essay suggests to me that NP-complete problems are much “harder” than BQP-complete problems, which would seem to suggest that algorithm 1 would need to take longer than algorithm 2. But Raz and Tal’s result seems to identify an oracle problem in BQP that is outside of the entire polynomial hierarchy (including all of NP), which would seem to suggest that algorithm 2 would need to take longer than algorithm 1. Which of these intuitions is/are incorrect?

How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem be $ \mathcal{NP}$ -complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or maximum) with target value in decision version. Thus, the decision version can be solved in poly-time as well. Since the decision version is $ \mathcal{NP}$ -hard, so is the optimization version, i.e., the optimization version is $ \mathcal{NP}$ -hard.

My question is how to prove the converse direction: if the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

I in advance thank you for any suggestions!

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially taking exponential time (2^P(n) where P is polynomial).

Moreover, can it be generalised to EXPTIME in general?

The reason I am asking this is that I wrote some programs to solve degenerate cases of an NPC problem, and they can consume very large amounts of RAM for hard instances, and I wonder if there is a better way. For reference see https://fc-solve.shlomifish.org/faq.html .

Proving a problem as NP-complete

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is “Do we also need to prove that problem X can be reduced to at least one NP problem?”. According to the NP-complete problem definition, each and every NP problem must be reducible to NP-complete problem. As problem X is NP, are we not supposed to prove that this NP problem can be reduced to other NP-complete problems? Why does this reduction have to be only one way to prove a problem is NP-complete?

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $ L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $ f:\Sigma^*\to\Sigma^* $ and there exists $ n\in\mathbb{N}$ such that for every $ x\in\Sigma^*$ satisfying $ |x|\ge n \implies |f(x)|\lt |x|$ .

Assuming $ P\ne NP$

Prove\Disprove: Every two NP-complete languages $ L_1,L_2$ are decreasing reducible.

I’d appreciate a hint or direction

Reduction from np-complete problem to unknown complexity problem and viceversa

Suppose I have two problems. B NP-complete, A of unknown complexity.


if I show that B <= A I can state that A is also NP-complete because the two required conditions are satisfied: (i) A is in NP (ii) i reduced a NP -complete problem to A.

if I show that A <= B I can say that B is at least hard as A, so A is at least NP-complete but can be harder.

Are these statements correct?

Prove NP-completeness for union of NP-complete language and language in P

Given disjoint languages $ X$ and $ Y$ , where $ X$ is NP-complete and $ Y\in P$ , how do I prove that $ X\cup Y$ is NP-complete?

My idea is to prove that $ (X\cup Y)\in NP$ and then prove that $ X\cup Y$ is NP-hard:

I can prove $ (X\cup Y)\in NP$ by saying that since both are in NP, they each have polytime verifiers. Thus we can have a polytime verifier that on any input will use these verifiers and accept if any accept, reject otherwise.

I am stuck on the part of proving NP-hardness. The idea of arbitrary languages is throwing me off; I am trying to reduce a NP-complete problem (SAT for example) to $ X\cup Y$ and using the fact that $ X$ has some method to reduce to it already but I am lost as for what to do with $ Y$ . I am thinking that given an input for SAT, I need to somehow change the input so that I can relate acceptance in $ X\cup Y$ to acceptance in SAT; same for rejection.

Any guidance would be appreciated; thanks!

Subset with modified condition, is it still NP-complete?

So i know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard. The given problem I have is subset sum. However, the conditions have been change to sum ≤ M and sum ≥ M from sum = M. My initial reaction is that the two problems are no longer NP-complete since they can both be solved within polynomial time.

  1. Check each element and see if there exists at least one smaller than M.
  2. Add all positive integers and see if the sum of all elements is larger than M.

Since it isn’t NP Hard, it cannot therefore be NP-complete.

Am I thinking/approaching this correctly?

Is it NP-complete to test if a graph contains $t$ $k$-cliques?

Let $ (G,t,k)$ – a graph with $ t$ cliques with $ k$ vertices (there are $ t$ cliques of size $ k$ in graph $ G$ ), for $ t,k > 100$ . How to prove that $ (G,t,k)$ is NP-complete?

It is obvious that it is in NP. I have tried to prove that $ k$ -CLIQUE language $ (G,k)$ is reducible to a $ (G,t,k)$ language. But I can’t get the idea, how to get $ t$ of $ k$ -CLIQUES.