New answers tagged np-complete
0
It is not entirely clear to me where the warehouses are allowed to be placed. I will assume here that a warehouse can be placed in any city given by the input1.
instead of minimizing the distance [$t$], I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?
Observe that we may assume the maximum allowed distance $t=1$, ...
0
Suppose that $X$ is a coNP problem which is NP-hard.
Let $A$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction from $A$ to $X$. Since $X$ is in coNP, this shows that $A$ is in coNP.
We have shown that $\mathsf{NP} \subseteq \mathsf{coNP}$. Now suppose $B$ is in coNP. Then $\overline{B}$ is in NP, and so in coNP. Hence $B$ is in NP. ...
1
I think you are trying to build the 2-SAT implication graph for 3-SAT.
In 2-SAT, $(x_a \vee x_b)$ may indeed be considered as 2 implications, $\neg x_a \Rightarrow x_b$ and $\neg x_b \Rightarrow x_a$.
The problem is that $(x_a \vee x_b \vee x_c)$ is not equivalent to any of the 6 implications like $\neg x_b \Rightarrow x_a$, as $x_c$ is sufficient to satisfy ...
1
BQP (the quantum analog of BPP) is closed under polynomial time reductions, so if some NP-complete problem is in BQP, then all NP-complete problems are in BQP. For more arguments, check this Quora question or that Quora question.
1
If you solve a Problem that is NP-complete the solution to this problem can not be applied instantly to any other Problem that is NP-complete. However, the problem that you solved might be used to find a solution for other problems in NP.
For example:
If you can solve the TSP Problem your an adaption of your solution could also solve the problem of finding ...
2
It seems like the OP is asking "what class of problems can be solved by a neural network"? It turns out that we have an answer.
First, realize that neural networks are "function approximators". In other words, a neural network is itself a function $\hat{f}$, which has been "trained" to mimic some function $f$ that we have ...
0
The other answers are correct, but to maybe add an intuitive perspective, you could imagine a neural network like a human brain, in terms of NP problem solving capabilities.
Both humans and neural networks are capable of "solving" hard problems "efficiently".
One distinction I want to make to what has been previously discussed here is ...
3
I think it is worthwhile to expand upon the “lucky guess” in reference to NP problems. That is a reference to the fact that NP problems are easy to verify. Instead of the typical factoring primes, let’s go with with a more down to earth problem. Say the year is 1970 and you want to know if there is a company that has 2 employees, one named Bob, one named ...
3
It is still $\mathsf{NP}$-complete.
Consider the following reduction from the normal $\mathrm{Clique}$ problem:
Given a graph $G$ and some desired clique size $k$, add a new vertex $v^\ast$ which is connected to all vertices of $G$ to obtain a new graph $G^\ast$.
Then $(G^\ast, k + 1, v^\ast)$ is a yes-instance of your modified $\mathrm{Clique}$ problem if ...
10
Let me start by briefly reviewing the kind of problems under discussion:
Problems in P: These are decision problems (where the answer is Yes or No), optimization problems (where the answer is an optimal solution to a problem such as minimum spanning tree), or function problems (compute some function of the input) which can be solved efficiently (in a ...
5
Non-linear optimization in general is not in NP, it isn't solvable at all. You cannot check in polynomial time whether a solution is the global optimum or just a local one. There is, in fact, no way to tell if your optimum is global, other than finding all of them (How would that work, how do you know how many optimums there should be, and what do you do if ...
4
Neural networks work reasonably well solving some kinds of problems. They are also awfully bad at solving other problems that they are used for.
Neural networks are totally incapable of solving NP complete problems beyond cases that can be solved by brute force, and not very good at this. There are optimisation problems where finding a good solution is ...
28
SGD is an algorithm, not a problem. It is not NP-complete or NP-hard. SGD is one approach to an optimization problem. Some optimization problems are NP-hard; some are not.
All of your deductions start from that one incorrect assumption, so they don't actually follow.
"Neural Networks" don't have a computational complexity; they aren't a problem.
3
However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from the same positions) evaluates to 0? All other subsets in T should evaluate to 1.
No, this is impossible. Consider $S=\{1,2,3\}$ and $W=3$. Our set $T$ should ...
2
The reason for why you are having problems is because your solution does not work. In particular, the problem is that your formula does not capture the VC problem statement. More precisely, the formula you build always has assignments satisfying $k$ clauses by just setting $k$ variables to true and the rest to false.
So let $G = (V, E)$ be a graph and $X \...
1
Firstly, note that you can reduce $CMCG$ to $MCG$ by setting the value of the node that must be in the set to the sum of all positive weights of all other nodes $+1$ and then applying $MCG$ and retrieving the result set. Thus $CMCG\in NP$.
As proved in the paper the $NP$-complete Steiner-Tree problem can be reduced to $CMCG$ meaning that $CMCG$ is $NP$-hard....
Top 50 recent answers are included
