3.108 complexity-theory questions.

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

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

10 Group isomorphism to graph ismorphism

In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For ...

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

3 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 Bounded occurrence 3D matching problem

1 answers, 71 views algorithms complexity-theory
It is NP-hard to approximate maximum 3D matching problem even if each element occurs exactly in two triples. I'm interested in the following decision version of 3D matching. Informally, Given a set ...

8 is P_CTC = BPP_PATH?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...

1 Trie traversal to maximise XOR in a tree but with a condition

Input:I am provided with x and y. x is a 32 bit non negative integer and y is some node-id of the tree. So, I built a trie with 32-bit non negative integer values which are the keys associated with ...

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

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

3 NP languages definition

2 answers, 46 views complexity-theory np
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 ...

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

1 Printing all paths of a tree and sorting the weight of edges

Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time. To solve this ...

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