Questions related to the (computational) complexity of solving problems
0
votes
0answers
14 views
Why checking if tuple belongs to join of two tables is NP-complete?
I have read that checking if tuple belongs to join of two tables is NP-complete.
I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. ...
0
votes
0answers
29 views
Is the following problem generalizing X3C?
The first problem is X3C for which I try to find out whether it's a special case of the second problem.
The second one is a stacking problem for which we have an itemset $I := \{i_1, ..., i_n\}$, $m$ ...
2
votes
1answer
17 views
Complete problem for $\mathrm{QP}$ (quasipolynomial-time solvable languages)
Question 1: Is it known that $\mathrm{QP}=\cup_{k}\mathrm{TIME}(2^{\mathrm{log}^k(n)})$ has any complete problem?
Question 2: Can this be used to simplify the computational complexity theory at all?
3
votes
1answer
83 views
Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?
Let
$$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$
Is $L_{300}$ decidable?
My intuition is it is decidable because given $M$ and $w$, we need ...
-3
votes
0answers
50 views
The Final Question: is P = NP? [on hold]
I heard my teacher say that many theorists tend to be inclined to P!=NP. Why it is that and what is your personal intuition about this topic?
Thanks
0
votes
0answers
24 views
Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped?
Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?
1
vote
0answers
19 views
Edge-midpoints cover with radius 1
This is in a series of posts. Previous quetion:
Vertex cover with covering radius 2
Other series: Karp hardness of searching for a matching split
In this problem, our cover for a given undirected ...
4
votes
4answers
141 views
Are there deterministic and/or non-interactive zero-knowledge proofs?
The Wikipedia page on zero-knowledge proof says
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a ...
-2
votes
0answers
9 views
Message complexity for a broadcasting algorithm
How many messages are sent in the distributed system if the StateXevent-->action is like this
initiator × SP → {send(I,N(x)) to N(x); become done}
idle × Receiving(I,Z) → {Process(I); become ...
5
votes
1answer
41 views
Vertex cover with covering radius 2
Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?
A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
1
vote
1answer
32 views
Polynomial Complexity (Relative to the Size of the Input)
I came across the following statement:
"Since b is smaller than n, the complexity $O((n + mb)^3)$ is polynomial."
I suppose it has something to do with the notion of polynomiality in terms of the ...
1
vote
1answer
25 views
Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$
I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$.
The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that ...
1
vote
1answer
55 views
Can we do 4-sum algorithm in O(n^2)?
this is related to the following question:
Generalised 3SUM (k-SUM) problem?
Without loss of generality, let's only consider even $k$, or just $k=4$.
My question is, after summing all pairs of ...
-1
votes
0answers
10 views
Is this restricted version of Fully Quantified Boolean Formula (FQBF) PSPACE-complete?
Given: A Fully Quantified Boolean Formula (FQBF) where the quantifiers of the Boolean Variables alternate between $\exists$ and $\forall$ from left to right in the problem.
Query: Is the above ...
1
vote
1answer
37 views
If the union and intersection of two NP languages are both in P, prove that the langauges are in co-NP
Given $L_1, L_2 \in NP$, $L_1 \cup L_2 \in P$ and $L_1 \cap L_2 \in P$,
Prove: $\ L_1, L_2 \in coNP$
What I've done so far is:
$$ L1 \cup L2 \in P \Rightarrow (L1 \cup L2) ^\complement \in P
\...
1
vote
0answers
21 views
What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?
Background
I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:
$$
\...
1
vote
1answer
16 views
The notion of PAC in approximation algorithms
In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is ...
3
votes
2answers
46 views
NP languages definition
Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not?
Because I need to have ...
4
votes
1answer
63 views
Karp hardness of searching for a matching split
UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
4
votes
1answer
30 views
Karp hardness of searching for a matching erosion
First, read the previous question: Karp hardness of searching for a matching cut
As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
-1
votes
0answers
39 views
About proof NL=L
Because my question is not clear and vague as indicated by Dr.I will rewritte it
First we know that the Problem of STCON is a complete problem in NL
So we have to make a DTM to solve it in a ...
0
votes
1answer
41 views
Examples of non-sparse languages
All I could find is an example of sparse language.
I understand that I need to design a language whose all strings generation should not be bounded by a polynomial function, but I feel all the ...
-1
votes
1answer
22 views
$\mathrm{ZPEXP} = \mathrm{BPP} \iff \mathrm{ZPEE} = \mathrm{BPE}$
Please, establish the above claim formally. It seems that the structure of complexity classes has so much bizarre features everywhere.
For the $\Longrightarrow$ direction, a padding technique will ...
0
votes
1answer
16 views
$\mathrm{BPEXP} = \mathrm{BPP} \iff \mathrm{BPEE} = \mathrm{BPE}$
Concerning about a wide variety of complexity classes, I have come up with the above conjecture.
Please, establish the claim in the title formally.
5
votes
2answers
76 views
Karp hardness of searching for a matching cut
Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split
Maximum Matching Cut problem
Input: An undirected graph $G(...
0
votes
0answers
21 views
Proof of the Cook-Levin Theorem - snapshot transitions
I'm trying to understand the proof of the Cook-Levin thereom in Aurora and Barak's "Computational Complexity" text.
A snapshot $z_i$ of $M$’s execution on some input $y$ at a particular step $i$ is ...
0
votes
0answers
34 views
If P=BPP, then Is it correct that IP=NP?
I'm now studying Interactive Proof System in Goldreich's textbook and here. I have the following question:
Suppose P=BPP, then this show that randomness doesn't give us power over deterministic ...
1
vote
1answer
9 views
$\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$
Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.
For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.
3
votes
1answer
21 views
Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak
In Computational Complexity -- A Modern Approach, by Arora and Barak, they have the following claim (Example 3.6).
Let EXPCOM be the following language
$$ \{ \langle M, x, 1^n\rangle \mid M \text{...
2
votes
1answer
43 views
Median of medians: bound on pivot position
If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at ...
1
vote
1answer
20 views
Does $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ imply anything?
The assumption $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ seems to yield nothing interesting at all. Is that true?
3
votes
1answer
27 views
Why not polynomial-space reductions for $PSPACE$-hardness?
A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$.
Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$.
Why does we use time reductions instead of ...
1
vote
1answer
33 views
Prove that it is undecidable whether a given LBA accepts a regular set
I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
2
votes
0answers
19 views
How to disprove that DTIME(f) = NSPACE(f)?
Is there an easy way (maybe by using hierarchy theorems) to disprove that $DTIME(f) = NSPACE(f)$ for any computable $f: \mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$?
1
vote
0answers
26 views
Sparse Matrix inversion without actual inversion
I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix?
Thank you ...
1
vote
1answer
79 views
P=NP giving a deterministic algorithm for SAT
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying ...
2
votes
1answer
15 views
Hardness of $2$ edge-disjoint spanning trees decomposition
The question is clear from the title. What is the complexity of the following decision problem:
Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two ...
2
votes
1answer
31 views
Show that RP is closed under concatenation
I'm trying to prove the following problem:
Show that $RP$ is closed under concatenation
Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
1
vote
2answers
49 views
How a NTM reject an input / How a TM simulates a particular NTM
I understood that a NTM can say only yes but it doesn't know if the input is a NO instance with a single execution. Furthermore, the NTM can diverges and, at the same time, can decide a language (...
0
votes
1answer
31 views
Relation of P vs. BPP and P vs. NP
What are the consequences of proving some relation ($\subseteq$, $\subset$, $=$, or $\neq$) on one of the following, to the other?
$P$ vs. $BPP$
$P$ vs. $NP$
1
vote
1answer
23 views
Constant-depth threshold circuit for $\mathrm{PP}$
Is it proven that $\mathrm{PP}$ has uniform constant-depth threshold circuit?
0
votes
1answer
18 views
Complexity classes that are low for equivalent definitions of $\mathrm{PP}$
What is the biggest complexity class that is low for each other equivalent definition of $\mathrm{PP}$?
I already know that $\mathrm{PP}^\mathrm{BQP}=\mathrm{PP}$. This is a lowness result using ...
3
votes
3answers
75 views
Oracle machine solving halting problem for other oracle machines
Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle ...
-3
votes
2answers
104 views
Does deep learning infer P = NP?
The question comes from the following scenario,
assume we have the traveler problem which is NP (the one where a traveler wants to visit all countries with the lowest cost(by summing up all flights))
...
3
votes
1answer
48 views
$TSAT$ is $NP$-complete
In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete:
$\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ ...
-1
votes
0answers
17 views
Time-constructible definition check for $T(n)=n$ and $T(n)=n^2$
In "Computational Complexity", a time-constructible function is defined as follows:
A function $T: \mathbf{N} \rightarrow \mathbf{N}$ is time constructible if $T(n) \ge n$ and there is a Turing ...
0
votes
1answer
22 views
Time-constructible functions definition
A function $T: \mathbf{N} \rightarrow \mathbf{N}$ is time constructible if $T(n) \ge n$ and there is a Turing Machine $M$ that computes the function $x \mapsto \lfloor T(|x|) \rfloor$ in time $T(n).$
...
-1
votes
3answers
80 views
How easy is it for computers to compute in a 4th Dimension (or more)?
I know its very hard to show a human what the 4th dimension would look like and the mind can't even comprehend more dimensions, but what about a computer?
How many "dimensions" can a computer handle?...
10
votes
2answers
168 views
Problems that feel exponential but are P
I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ...
2
votes
1answer
18 views
Exponential Space Complexity equality
Consider $$ \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE}(2^{c (\log{n})^2}) \quad \overset{?}{=} \quad \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE} ( n^{c \log{n}})$$
My lecture notes say that this is ...
