## How to prove that this problem is NP-complete (or NP-Hard)

I have the following data:

• A set $$V$$ of tasks, the starting time $$s_j$$ of each task and the duration $$p_j$$ of each task.

• A set $$K$$ of resource, each resource has an availability function $$R_{k}$$ that is piecewise constant.That is, for each $$t = 0, .., T-1$$, we precise $$R_{k}(t)$$ the number of units available at $$t$$. $$R_k$$ is an array of length $$T$$.

• Each task $$j$$ needs $$r_{j,k}$$ resources to be processed (it could be zero). This quantity needs to be available during all the processing time starting from $$s_j$$.

For example consider :

• Task$$A$$ has processing time $$3$$ and starts at time period $$t=2$$ and needs 2 units of some resource $$k$$
• Task $$B$$ has processing time $$4$$ starts at time $$t=3$$ and needs 3 units of the same resource $$k$$.

Then if $$R_{k}(t) = [*,*,2,6,6,3,*,*]$$ then we are ok since at time $$t=2$$ only task $$A$$ is active and it requires $$2$$ units, at time $$t=3$$, both tasks are active and the sum of their utilization is $$2+3 = 5 \leq 6$$; same at time $$t=4$$. At time $$t=4$$, only task $$B$$ is active and it requires $$3$$ units.

However, if $$R_{k}(t) = [*,*,2,4,6,3,*,*]$$, is not ok since at time $$t=3$$, both tasks $$A$$ and $$B$$ are active and their total use is equal to $$5$$ wheras only $$4$$ units are available.

Here is my attempt to verify that the resource utilization at each $$t$$ is no larger than the availability function. So the answer is yes or no (we can say that this is a decision problem).

For each time t in [0,T-1]   For each resource k in K      total_use = 0, active_set = A     for each task j in V       if s_j<=t and s_j+p_j > t and r_{j,k}>0 \if the task is active at time t and it requires positive amount of resource k in order to be processed)         total_use += r_{j,k}         active_set := active_set U {j}        if total_use > R_{k}(t)         print(at time t the usage of resource k exceeds its capacity, active_set)         return False return True 

The algorithm here is pseud-polynomial. Unfortunately, I need to find a polynomial one in order to say that the problem is in $$\mathcal{NP}$$.

## Is “Solving two-variable quadratic polynomials over the Integers” is an NP-Complete Problem?

On this Wikipedia article, it claims that given $$A, B, C \geq 0, \; \in \mathbb{Z}$$, finding $$x, \,y \geq 0, \, \in \mathbb{Z}$$ for $$Ax^2+Bx^2-C=0$$ is NP-complete? Given by how easy I can solve some (with nothing but Wolfram), it doesn’t seem right. I’m sure it’s either written incorrectly or I’m just misunderstanding something.

Posted on Categories proxies

## NP-Complete Problem and Polynomial Hierarchy

I have tried to search the internet to check if the following is correct: If $$\sum_{2}$$ contains a NP-Complete problem then PH collapses to NP: $$PH=NP$$

For example if $$SAT\epsilon\sum_{2}$$ than: $$PH=NP$$

Posted on Categories proxies

## Can an NP-Complete problem be reduced to an NP problem?

All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?

## If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

• If problem B is in P and A reduces to B, then problem A is in P.
• Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
• Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

My questions are (if I then II then(?) III/I. If III/I and III/II then IV.)

• I: Are there a generalized form to reduces NP problem to either P or NP-complete?
• II: Are there a certain number of NP-complete problems?
• III/I: Are all of the NP-complete problems can be reduces to all other NP-problems?
• III/II: If we can reduce B in NP-complete problem to A in P, can we prove that all problem reduces to B is in P?
• IV: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?
Posted on Categories proxies

## If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

I searched a lot on internet, including here, but I couldn’t find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-complete, can I say that A is NP-complete too?

Actually, I would say yes, because if I can convert a problem that I don’t know how to solve to one that I know, then that problem must be at least as hard as the reducible one. So, A should be NPC.

However, I got to another idea that I can convert an easier problem to a hard one, so I could say that A is NP, but I couldn’t guarantee that it’s NPC.

Which ideia is correct?

Posted on Categories proxies

## Is it possible to train a neural network to solve NP-complete problems?

I’m sorry if the question is not relevant, i have tried to search for articles about it but i couldn’t find satisfying answers.

I’m starting to learn about machine learning, neural networks etc … and i was wondering if making a neural network that takes a graph as input, and output the answer of an np-complete problem (e.g. the graph is hamiltonian / the graph has independant set superior to k, and other decision problems) would work ?

I haven’t heard of any np complete problems being solved like this, so i guess it does not work, are there theoretical results stating that a neural network cannot learn np-complete language or something like this ?

Posted on Categories proxies

## Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

I have a set $$M$$, subsets $$L_1,…,L_m$$ and natural numbers $$k,l\leq m$$.

The problem is:

Are there l unique indices $$1\leq i_1,…,i_l\leq m$$, such that

$$\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}\right| \leq k$$

Now my question is whether this problem is $$NP$$-complete or not. What irritates me is the two constraints $$l$$ and $$k$$ because the NP-complete problems that were conceptually close to it that I took a look on (set cover, vertex cover) only have one constraint respectively that also appears in this problem.

I then tried to write a polynomial time algorithm that looks at which of the sets $$L_1,…,L_m$$ share more than $$k$$ elements with other sets but even if all sets would share more than $$k$$ elements with other this wouldn’t mean that their intersection has more than $$k$$ elements…

This question kind of comes close but in it there is no restriction on the amount of subsets to use and the size of the intersection should be exactly $$k$$, but maybe this could be useful anyways.

Can somebody further enlighten me ?

Posted on Categories proxies

## How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC

Posted on Categories proxies

## Assuming the Exponential time hypothesis is true, what’s the fast possible algrotimh’s that can be produced for NP-complete problems [duplicate]

Assuming the Exponential time hypothesis is true, what’s the fast possible algrotimh’s that can be produced for NP-complete problems?

If 3-Sat takes exponential time, then could it be possible that some NP-complete problems can be solved in $$n^{log^k(n)}$$ time? $$2^{n^{1/log(log(n))}}$$ time? $$2^{n^{0.5}}$$ time?

Posted on Categories proxies