Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,756
questions
1
vote
1answer
36 views
Why exactly is Zero Knowledge Proof used here?
"The Ali Baba cave" example of ZKP is pictured below. There is no need for a probabilistic ZKP protocol to prove to the verifier of the statement (that the prover has the key to the door). ...
0
votes
0answers
14 views
Limited number of calling for a decision blackbox to compute all the solutions
I am trying to reduce between a solution problem and a decision version of the same problem.
The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
1
vote
0answers
16 views
Are there more efficient recognizers for the halting problem?
Define the halting problem as $\{\langle M, w\rangle: \text{$M$ is a TM that halts on $w$}\}$. It is undecidable, but recognizable, with a naive recognizer that simulates $M$ on $w$. In a certain ...
0
votes
0answers
13 views
Turing machine with polynomial complexity on Jflap
I would like to ask a question: I have this very simple Turing machine. Simply by subtracting the numbers A and B, given the input M (A, B, C, D) =.
Using the Step function on Jflap, complete the ...
0
votes
0answers
22 views
Sum of asymptotic notations
Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$?
Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
3
votes
0answers
30 views
Linear time complexity
We know from the linear-speedup-theorem that
NTIME($\mathcal{O}(f)$) = NTIME($f$) and DTIME($\mathcal{O}(f)$) = DTIME($f$),
given that $f(n) > (1+\varepsilon) n$ for some $\varepsilon\in\mathbb{R}$....
0
votes
0answers
25 views
Modern proof of Goldwasser-Sipser IP[n]=AM[n+2]?
The original paper by Goldwasser and Sipser proved IP[Q(n)]=AM[Q(n)+2].
Is there some modern source that proofs the theorem? (The full theorem and not specific cases such as limiting the number of ...
1
vote
1answer
40 views
find 3 points among some given 2D points such that the triangle includes another given point
Ideally, these would be the points that form the smallest (nondegenerate or degenerate) triangle. However, I can admit a large amount of approximation to get it to a lower order of complexity.
I can ...
1
vote
1answer
37 views
Why is SET PACKING in NP?
I have seen an lot of proves why SET PACKING is NP complete. However, in every prove it states that SET PACKING is clearly in NP. It might be a stupid question, but is not so clear to me. I see that ...
1
vote
0answers
19 views
Conflict Clusters – Another P=NP Proof [closed]
Conflict Clusters – Another P=NP Proof
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a ...
2
votes
1answer
52 views
Maximum independent subset for graphs with lots of edges
Consider an NP-hard graph problem, like the maximum independent set problem.
Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
3
votes
1answer
62 views
Can it be NP hard to calculate the value of a function?
So, I've just begun dabbling in complexity theory and I'm somewhat confused as to the relationship between NP-hardness and function computation. As far as I've understood, NP-hardness is defined for ...
1
vote
1answer
40 views
Does a set definition have computational complexity?
I'm wondering if a mathematical set definition has a computational complexity.
For example, assume I have some kind of problem where the solution is given by the positive integers smaller than a given ...
2
votes
1answer
27 views
Reducing a CNF formula to a DNF formula in less than exponential time
The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently.
My idea is based upon the ...
1
vote
1answer
17 views
A query regarding Definition of Circuit Family and Languages
This is a query regarding the definition of Circuit Family and Language (in the same Context). The textbook definitions of each are:
Language: A function whose inputs and outputs are a finite bit of ...
1
vote
0answers
25 views
Graph based on strings of turing machine
For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
1
vote
1answer
15 views
Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?
I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean ...
4
votes
1answer
68 views
Attempt to reduce to problem of inner product
The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$?
The problem of max product: likewise two sets each $n$ vectors (...
1
vote
1answer
53 views
Whether and how to distinguish two kinds of $O(1)$ speedup
Here is a very bad algorithm that computes $4n$ for an integer input.
...
2
votes
2answers
88 views
What if solving P vs NP revealed a contradiction?
Let's just say that some person discovered that $P = NP$ implies $P \neq NP$ and $P \neq NP$ implies $P = NP$, and we don't know what is causing this contradiction, And this was a valid proof that was ...
1
vote
2answers
41 views
What are some problems in EXP not known to be EXPTIME-Complete, but also do not have any known algorithm in NP?
These would be problems known to be in exp where there could hypothetically be a P or NP algorithm, but none have been discovered yet if one is possible.
-2
votes
2answers
172 views
What are some problems in EXPTIME not known to be EXPTIME-complete?
Not problems like chess. I'm thinking problems that would be very useful to be able to solve in sub-exponential time. These would be problems not known to be EXPTIME complete.
Edit I mean problems ...
0
votes
1answer
36 views
Combination of two Languages in a arbitrary complexity class
Given two unrelated languages $L_0$ and $L_1$ contained in some complexity class $C$. Is the language $L_x=L_0\times L_1= \{(x,y)|x\in L_0, y\in L_1\}$ always contained in $C$?
And if that is the case,...
0
votes
0answers
18 views
NC with nearest neighbor gates
Consider a circuit belonging to the class $\text{NC}^i$, as defined here.
From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
0
votes
1answer
27 views
Sum of a function Θ(g) with a function that is not O(g)
Consider g a function of n: $g(n)$.
Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + ...
1
vote
1answer
39 views
Importance of $\Sigma^P_2=PSPACE$
Assuming (the unlikely scenario) that the Polynomial Hierarchy collapses to second level. Thus, $\Sigma_2^p=PSPACE$.
How significant this result would be (broad consensus) as compared to the other ...
5
votes
1answer
486 views
Why are $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ compatible?
If $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ are both true then $\sf{P}$, $\sf{NP}$ and $\sf{coNP}$ are three separate complexity classes. In other words, verifying a solution, finding a ...
3
votes
1answer
55 views
Relation between $P$ vs $\mathit{NP}$ and $P^{\mathit{NP}}$ vs $\mathit{NP}^{\mathit{NP}}$ questions?
Given that both $P \subset \mathit{NP}\ ?$ and $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}\ ?$ are open questions.
Is it possible that
$P \subset \mathit{NP}$ and $P^{\mathit{NP}} =\mathit{NP}^{...
0
votes
0answers
38 views
pseudo-dimension for knapsack problem
Let $v_i, s_i$ be the value and size of item $i$, let $\rho \in \mathbb{R}$, n be the maximum number of items. Then we add items based on $\frac{v_i}{s_i^{\rho}}$ in decreasing order. I was trying to ...
30
votes
1answer
3k views
Problems that are polynomially "hard" to compute but "easy" to verify
In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
1
vote
1answer
20 views
Can I reduce from the recognition version of one probem to another without knowing the exact parameter?
I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
0
votes
1answer
29 views
Help in proving L-Completeness
I'm trying to prove that the following language is L-complete
A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's
So far I've managed ...
0
votes
1answer
32 views
What would be the conseuqences of BQP = NEXPTIME?
On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly ...
1
vote
2answers
57 views
What's wrong with the reduction from integer programming to linear programming?
I'm confused with polynomial-time reduction and NP-hardness.
Let's say that the following integer programming is NP-hard.
$\min_{x \in K} f(x)$, where $K$ is a finite subset of $\mathbb{N}$.
But it is ...
1
vote
2answers
35 views
We cannot recognize a set of languages as the language themselves
"We cannot recognize a set of languages as the language themselves"
What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
0
votes
0answers
35 views
Algorithm for the specific problem
A problem : Given a string of number in base $10$ we want an algorithm to calculate the number of numbers, where we replace (only) a single digit to produce a number so that that number is divisible ...
2
votes
0answers
32 views
Non-trivial reduction form SAT to $3$-SAT
Looking for any idea for reduction from $SAT \leq 3-SAT$ where $SAT$ is known to have $d$ variables at most in each clause. I am looking for a reduction in which the resulting formula will not depend ...
1
vote
0answers
19 views
Finding square root of a gram matrix over the integers [closed]
Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that $A = B \...
1
vote
0answers
44 views
Algorithm to find maximum sum over weighted overlapping intervals
Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
6
votes
1answer
117 views
Prove TILING is NP-Complete
I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, ...
1
vote
1answer
36 views
Is Self-Modifying Turing Machine equivalent to NTM or TM?
Let SMTM be Turing Machine, but the commands recorded in which can change to others in some random way (for example, choose with a 50/50 probability the command to move to the right or move to the ...
0
votes
1answer
28 views
What are some examples of problems in R but not in PR?
Also are there any R complete problems? These would be the hardest decidable problems to my knowledge. Sorry if this isn't specific enough.
3
votes
1answer
141 views
A complexity class between P and FPTAS
The question is about approximation algorithms to NP-hard optimization problems.
For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the ...
1
vote
1answer
25 views
About NP-completeness and reduction
Probably this is a basic question but I'm not sure how to finish this proof. I have a problem $X$ and I want to prove that it is possible to reduce $X$ to another problem $Y$. I know that $Y$ is NP-...
2
votes
1answer
35 views
find vertex cover of size at most 30 of a graph
This is a question from an exam I got wrong. Given an undirected graph $G$. Consider the decision problem of finding if there exists a vertex cover of size at most 30. Can we find a polynomial time ...
1
vote
0answers
22 views
How to show perfect completeness of the Set Lower Bound Protocol?
In these lecture notes (on page 5 under "Some Remarks") it is claimed that the Set Lower Bound Protocol (given there on page 4) can be modified to have perfect completeness. However, while I ...
2
votes
1answer
12 views
Question on worst-to-average-case reductions
Consider two decision problems A and B.
We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A.
Now, let's say it is known that the worst case instances ...
-2
votes
2answers
107 views
If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?
The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
2
votes
0answers
26 views
On the complexity of equitable $k$-coloring split graphs
The Wikipedia article on Equitable coloring states that
A polynomial time algorithm is known for equitable coloring of split
graphs.
The referred paper also seems to achive the proposed polynomial ...
0
votes
0answers
15 views
Bin packing (NP-Complete)
I'm working on a project over Bin packing being NP complete, I understand the full reasoning behind it (algorithmically), but I need to know what's a proper explanation for the Bin packing being NP ...
