New answers tagged complexity-theory
0
If you prove that P=NP then proving the opposite is not just harder, but impossible.
-2
I believe it is impossible to prove P<>NP, because you would have to rule out all algorithms that could prove P=NP. There could be an infinite number of these possible. There is no way to disprove infinity, therefore it’s not possible. On the other hand all it would take is a single algorithm to prove P=NP, if it is so. Therefore, either P=NP which ...
3
Given a CNF with $n$ variables and $m$ clauses, we denote by $A_i$ the set of truth assignments that do not satisfy clause $i$. Then the number of satisfiable assignments is
$$2^n-\left|\bigcup_{i=1}^m A_i\right|.$$
Since each assignment makes at most one clause false, $A_i$ and $A_j$ are disjoint for $i\neq j$. Also note $|A_i|=2^{n-n_i}$ where $n_i$ is ...
2
Separations are known for constant-depth circuits. One recent result in this area is due to Bravyi, Gosset, and Koenig (see also the journal version in Science). Recent independent works by Bene Watts, Kothari, Schaeffer, and Tal, Coudron, Stark and Vidick, and Le Gall strengthened the hardness result for classical circuits from worst-case hardness to ...
0
Aryabhata's answer can be fixed up by making use of the fact that we can multiply all the numbers by some large $c$, and then add something small to each one to act like a "presence tag", and then supply some extra numbers that will allow us to get to zero if we could get to $cK$ without them. Specifically, we will use $c=2(n+1)$ and 1 as the presence tag.
...
0
Alternatively show for every k: There is no w containing 2k+1 d’s.
0
Just to give a heuristic argument, based on practical experience.
Almost all instances, of almost all NP-complete problems, are easy to solve. There are problems where this isn't true, but they are hard to find, and it's hard to be positive you have sound such a class.
This has come up in practice several times when people try to write random problem ...
0
The proof is by induction on the length of $w$. If $|w| \leq 2$ then necessarily $w = a$ or $w = b$, and in both cases $w$ doesn't contain any $d$'s. If $|w| \geq 3$ then necessarily $w$ is of the form $ducvd$, where $u,v \in L$ are shorter words. By induction, each of $u,v$ contains an even number of $d$'s. It follows that $w$ also contains an even number ...
2
All that you know is that R is NP-hard.
To show that R is NP-complete, you need to show that it is in NP. But that is not automatically true.
As an example, let S be the question "Is there a path of cost at most l that visits every node of a graph G?" and R be the question, "What is the cheapest path that visits every node of a graph G?" These are ...
2
do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations?
$3-SAT$ is known to be solvable in time $O(1.321^n)$. Therefore, there is no instance that would force a $\Omega(2^...
3
It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".
-4
Here is working code. Don't forget to input your percentage in fractional form (e.g. $0.02$ for $2\%$).
#include <stdio.h>
#define MONTHS_IN_YEAR 12
float monthlyRepaymentAmount(float principalAmount, float interestRate, int numberOfYears);
int main(void) {
//Problem statement variables
float principalAmount; // use int if principal can ...
2
Yes. Using L'Hospital:
$\lim_{n \rightarrow \infty} \frac{\ln^k (n)}{\sqrt n} = \lim \frac{k \ln^{k - 1} (n) \frac{1}{n}}{ \frac{1}{\sqrt n }} = \lim \frac{ k \sqrt n \ln^{k -1 } (n) }{ n } = \lim \frac{k \ln^k (n)}{\sqrt n} = \dots = \lim \frac{k \cdot (k -1) \cdot \dots \cdots 2 \ln (n) }{ \sqrt n} = \lim \frac{k! \frac{1}{n}}{\frac{1}{\sqrt n}} = \lim \...
2
You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.
So. We have some DFA $M$, and we can build a PDA $N$ which ...
1
Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to $L$. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:
Run $M$ on the empty input.
If $M$ halts, interpret the input as a Turing machine and run in on the empty input.
If $M$ doesn't halt on the empty input, ...
0
There are special cases of convex problems that can be solved in polynomial time, e.g. a convex QP defined over a simplex. In general, however, convex programming is NP-hard. However, NP-hard by no means means unsolvable.
Although theorists would probably cringe at the term, there are NP-hard and what I coin as "NP-harder" problems. What I call an NP-harder ...
1
It’s a 3x3 matrix, so it can be done in constant time O(1). I can’t see where a “k” comes into this problem.
0
Since you are subtracting $Z$ from $I$, you must compute the lower part of the matrix. If it was reversed, you only had to compute the new diagonal. The total number of subtractions is therefore $(k^2 + k)/2$.
2
As confirmed independently in another answer, 2P2N-3SAT is already NP-complete. Another name for the fragment you are interested in is (3, B$k$)-SAT where "B" stands for Balanced and indicates that there are the same number of positive and negative occurences of the variables, $k$ is the number of positive and the number of negative occurences, and the 3 ...
3
Why is $1$ returned with probability $33\% < \frac{1}{3}$ and not with probability $\frac{30}{30+90} = \frac{1}{4}$?
Anyway, this can be done in $O(NU)$ space (assuming $i_1, \dots, i_{NU}$ each fit in $O(1)$ memory words) and $O(1)$ time (assuming you can sample an integer between $1$ and $\sum_{j=1}^{NU} i_j$ uniformly at random in $O(1)$ time) using ...
5
If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}[O(n^k)]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and ...
3
Here is an informal proof, which you can try to formalize.
Suppose that we’re looking for 1 in an array of length $n$ of 0s and 1s. We consider the following distribution: each element is 1 with probability $1/n$. (You can also try your luck with the uniform distribution over all arrays with a single 1.)
Given the transcript of the algorithm, you can ...
4
The reason it's common knowledge and not formally proved anywhere is because it's obvious.
During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time.
I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time ...
1
Your reduction $f$ works in nondeterministic logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete.
What might be confusing you is that PSPACE=NPSPACE, which is ...
2
As j_random_hacker suggested, we can reduce MAX-2-SAT to this problem.
Given an instance of MAX-2-SAT with $n$ variables $x_1,\ldots,x_n$ and $m$ clauses, we can encode it as the following constraints:
For each variable $x_i$, add $m$ identical constraints: $x_i\le 0$ (if identical constraints are not allowed, we can use $x_i\le 0,x_i\le 0.1,x_i\le 0.01,\...
0
Instead of having a constraint $C_j: \sum b_{ij}x_i ≤ c_j$, introduce another variable $y_j$, change the constraint to $\sum b_{ij}x_i ≤ y_jc_j$, add a constraint $y_j$ ≤ 1, maximise the sum of $y_j$ (everything straightforward so far), then add a requirement that $y_j$ must be an integer.
If you fix all mistakes that I may have made :-) then checking that ...
1
$f(a,b)=\sum_{k=1}^b \log(k*\frac{a}{b})=\log\prod_{k=1}^b \left(k*\frac{a}{b}\right)=\log \frac{b!*a^b}{b^b}=\log(b!)+b\log\frac{a}{b}=b\log a +[\log(b!)-b\log(b)]$
by Stirling's formula, $\log(b!)=b\log b -b +\mathcal{O}(\log{b})$
Therefore $f(a,b)=b\log a +o(b\log a)$ so $f(a,b)\sim b\log a$
NB: all asymptotics ($\sim$, $\mathcal{O}$ and $o$) are taken ...
0
The complexity of the former is constant. Since we are talking about an Arithmetic Series (a finite sequence of numbers where the difference between any $i+1$ and the $i$ element is constant) the sum can be calculated as half of the product between the number of elements in the sequence and the sum of the first and last
$$ \text{Given a sequence of numbers ...
3
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L \in NP-complete$. define $L'=\{1^{n^c-n}l| l\in L\& |l|=n \}$ it is easy to prove that $L' \in NP-complete$ and there is a $O(2^{\sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $...
6
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(\sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(\sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/...
4
As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know.
As you can see there, the complete statement of Baker, Gill, Solovay is:
There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$
The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "...
0
A problem $\Pi$ is $\textrm{NP}$-hard if every problem in $\Pi' \in \textrm{NP}$ can be reduced to $\Pi$ via a Karp reduction $\le_p$, i.e., if $\Pi' \le_p \Pi$.
A problem $\Pi$ is $\textrm{NP}$-complete if it is $\textrm{NP}$-hard and belongs to $NP$.
Intuitively, a $\textrm{NP}$-complete problem is as hard as the hardest problem in $\textrm{NP}$ while a $...
0
Dividing a 128 bit number by a 64 bit number can be done in constant time. If N is a prime that doesn't fit into 128 bit then the algorithm won't finish in your life time :-) Dividing two n bit integers can be done in O (n log n) for large n.
But assuming that you use brute force division that does use $O (n^2)$ operations for a division, then you should ...
0
It is $(\lfloor \sqrt{N} \rfloor-1) \cdot O(n^2) = O(\sqrt{N} \log^2 N) = O(2^{\frac{n}{2}} n^2)$ in the worst case: for each of the $O(\sqrt{N})$ choices of the dividend you perform a division of two numbers of at most $n$ bits.
(When you factor $N$ you might repeat some of the divisions, but these can be safely ignored since there can be at most $n$ ...
3
Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here)
That's not odd at all: it's because no such proof exists. Anything that can ...
4
The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; ...
0
Ok I think I got it know.
If I could reduce a NP-complete problem to a coNP-complete problem every problem in NP can be reduced to every coNP-complete problem and it would show that NP is a subset of coNP.
Because every problem A in coNP has a complement co_A in NP
A in coNP => co_A in NP => co_A in coNP => A in NP
=> every Problem in coNP is in NP
=> ...
1
In short
yes
Proof
Let's assume $X$ is NP-complete and $X$ is in co-NP.
We show that $NP \subseteq coNP$ and viceversa.
[$NP\subseteq coNP$]
Because $X$ is NP-complete
$=>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$.
But $X$ is in coNP
$=>$ for the polityme reduction closure of coNP, $L\in coNP$ too
$=&...
2
A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.
Tractability of convex problems essentially boils down to being able ...
0
In the case of the travelling salesman problem, you can easily write unit test that find _ some_ bugs but not all: construct an instance and find a solution. Then increase some distance between cities that are part of the optimal solution and solve again. The shortest distance should not become less. And then you repeat.
An algorithm that doesn’t find an ...
0
The Turing test would make a very poor unit test because (a) it is difficult (impossible ?) to automate and (b) the evaluation of the test output to produce a pass or fail result is subjective. In fact, it might not even be possible to devise useful unit tests (in the usual sense) for strong AI - how would unit tests distinguish between true AI and a program ...
Top 50 recent answers are included
