Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...