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.

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?

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?

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 ?

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 ?

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?