Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,201
questions
-1
votes
1
answer
601
views
Is finding negative cycle vertices NP complete?
I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in ...
- 99
-1
votes
1
answer
154
views
How do we know that all NP problems reduce to NP-hard problems? [duplicate]
For example, how is it proven that any NP problem can reduce to subset sum, circuit satisfiability, etc.? Or could you link to a proof?
-1
votes
1
answer
34
views
A sufficient condition for unsatisfiability
Let $\varphi = \bigwedge C_k$, in which $C_k$ is a clause in X3SAT (exactly-one 3SAT or one-in-three 3SAT). That is, $C_k = (l_i \odot l_j \odot l_u)$ such that $l_i \in \{x_i, \overline{x}_i\}$ for ...
-1
votes
1
answer
40
views
Prove the NP-hardness of problem
Prove the $NP$-hardness of $CONNECTEDNESS$ - the problem of counting over an oriented graph $G$ and two vertices
$s$ and $t$ the number of subgraphs of $G$ in which from $s$ to $t$ can be traversed by ...
- 1
-1
votes
2
answers
77
views
Is P vs NP, a paradox in a hypothetical perspective?
In a hypothetical scenario, where a precise and formal definition does not exist here, and thus expressed with analogies and verbal reasoning for the sake of simplifying the P, NP problem.
A(lan) ...
-1
votes
1
answer
50
views
What is the complexity of determining whether a graph has a maximal clique of a given size?
What is the complexity class of: given a graph G, is the graph has a maximal clique of size k? k is integer less than or equal the number of graph vertices.
A related question,
Given a Graph G, Find a ...
- 1
-1
votes
1
answer
21
views
-1
votes
1
answer
42
views
Can you help me find some examples of 3co-SAT for 4 variables?
I've been studying the examples of 3co-SAT recently.
It's easy to find an example of one variable.
$(x_1\lor x_1\lor x_1)\land (\overline{x_1}\lor \overline{x_1}\lor \overline{x_1})$
Examples of 2 ...
- 195
-1
votes
1
answer
45
views
Complexity of T(n)=2T(n-1)
I built a recursion tree like this:
0
/ \
0 0
/\ /\
... ...
So the tree has height n, and width $2^n$.
But if the sum of all levels is $\sum_{i=0}^{n}...
- 1
-1
votes
1
answer
77
views
How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?
The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
-1
votes
1
answer
48
views
Are the following assertions true if P != NP?
We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold:
$MST^* \le_{P} ...
-1
votes
1
answer
30
views
What is the generated grammar for this language?
I want to construct a regular grammar that generates words that contain both "ab" and "bc" as subwords with the alphabet of the terminal symbols {a,b,c}
My solution so far is
G=(Vn=...
- 15
-1
votes
2
answers
2k
views
Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$
I tried many grammars and so far I got this one:
\begin{align}
&S \to aXbZ \mid abc \\
&XZ \to Ybcc \\
&Xb \to bX \\
&bY \to Yb \\
&aY \to aa \mid aaX
\end{align}
Is my grammar ...
- 15
-1
votes
1
answer
116
views
Time complexity problem
Let Σ = {0, 1} and let A ⊆ Σ* be a language contained in DTIME(4n), and define
B = {xx | x ∈ A}.
(a) Show that B ∈ DTIME(2n).
(b) Prove that A ≤pm B.
I'm new to complexity theory. how can I show ...
- 1
-1
votes
1
answer
87
views
Algorithm to find array elements that a[i] > 2a[j] with i<j
Im trying to find an algorithm which returns array elements that a[i] > 2a[j] with i < j in O(nlogn). I can think how to implement this algorithm using double for but i cant implement it in O(nlogn)...
- 101
-1
votes
1
answer
74
views
A simple clarification on polynomial hierarchy
$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$ holds. So according to current knowledge is following true?
$P^{\Sigma_2^P\cup\Pi_2^P}\subseteq ...
- 2,862
-1
votes
1
answer
50
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.
user92914
-1
votes
1
answer
38
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 ...
- 2,245
-1
votes
1
answer
113
views
What will be the computational complexity of a system with two pipelined algorithms?
A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ...
- 99
-1
votes
1
answer
111
views
Show that a problem belongs to NP
A logistics company has two trucks and has to deliver some packages to some addresses. The manager has to create a plan for every driver.
Input Data: A set of V locations, an array d[v,u] for every ...
- 139
-1
votes
1
answer
103
views
On NP and PP in RP?
Does $NP\subseteq RP\implies NP=RP$?
Does $PP\subseteq RP\implies \oplus P=NP=RP$?
At least what additional minimal conditions will give truth of above?
- 2,862
-1
votes
1
answer
157
views
Given three infinite languages L1 L2 L3 over the same Alphabet, that do not intirsect. could one be TR and the other TD and the third neither?
$\sum$ is the Alphabet of three infinite languages $L_{1},L_{2}$ and $L_{3}$
where $L_{1}\cup L_{2} \cup L_{3}=\sum^{*}$
and
$L_{1} \cap L_{2} = \emptyset$, $L_{2} \cap L_{3} =\emptyset$ and $...
- 335
-1
votes
1
answer
43
views
Why is $MOD_{p^k}P=MOD_pP$ at every prime $p$?
Complexity zoo states that $MOD_{2^k}P=MOD_2P$.
It is clear that if $MOD_2P$ accepts (number of accepting paths is off) then $MOD_{2^k}P$ accepts.
Why is it clear that if $MOD_2P$ rejects (number of ...
- 2,862
-1
votes
1
answer
107
views
Does NP ⊆ Co-NP imply NP = Co-NP?
Does NP ⊆ Co-NP imply NP = Co-NP?
And also, does Co-NP ⊆ NP imply NP = Co-NP?
And does either statement imply P = NP?
Thank you very much in advance.
-1
votes
1
answer
2k
views
Prove that Integer linear programming (ILP) is in NP
Help is needed, I've tried to solve it by myself but I could find any reasonable solution which is solid enough. this is what I've wrote:
Consider a 0-1 ILP, where each variable x1,x2...,xn can ...
- 131
-1
votes
1
answer
207
views
Check if $P^{NP} = P^{coNP}$
Check if $P^{NP} = P^{coNP}$
To my eye answer is "unknown".
I would try to show that it implies that $coNP=NP$, what is unknown fact.
Lets suppose that $P^{NP} = P^{coNP}$. Then we use simply ...
-1
votes
1
answer
332
views
Query regarding PP complexity class vs NP?
Considering the complexity classes $NP$, $co-NP$ and $PP$:
$NP$ and $co-NP$ are both contained in $PP$.
For any Language $L$ suppose we have the mechanism that: If the oracle of $co-NP$ implies $No$ ...
- 715
-1
votes
2
answers
105
views
Not sure which NPc problem to use for NPc reduction problem,
I'm attempting to prove a problem is NPc, but I'm not sure which one would be optimal to use,
The problem is:
There are $n$ boars to be caged, and $m$ cages which each cage being able to hold $k$ ...
- 1
-1
votes
1
answer
86
views
Showing that given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$ is NP-complete
Let be the following problem : "Given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$. Show that it is NP-Complete
I know how to show that
a set of ...
-1
votes
1
answer
297
views
Reduce knapsack to problem with {0,1}-Matrix
I'm looking for a problem, where i can reduce the knapsack feasibility problem:
$$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$
to a problem, where i have a matrix ...
- 1
-1
votes
1
answer
66
views
Proving that the set of non-universal CFGs is not in NP
How do I prove that $\overline{\mathrm{ALL_{CFG}}}$ does not fall in NP, where
$\qquad\mathrm{ALL_{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^* \}$
-1
votes
1
answer
142
views
Prove NP Complete
There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete?
Solution: I can prove that it ...
-1
votes
1
answer
366
views
Solving a Variation of knapsack [closed]
I'm working on a problem which to me, seems very similar to a knapsack problem:
A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store ...
- 175
-1
votes
1
answer
114
views
NP hardness of Partition
I'm trying to show that PARTITION is NP-hard. I'm not sure if what I have is correct so I'll write what I have. I tried to reduce it from SUBSET_SUM:
$$PART= \{S\subset\mathbb{Z}|\exists C \subset S: ...
- 339
-1
votes
1
answer
60
views
Fixed Parameter Algorithms
Suppose a parameter $\hat{k}$ is larger than another parameter $k$, assume that $k$ is bounded
by a function $f$ of $\hat{k}$.
How can we prove that if a problem is FPT with respect to $k$ implies ...
- 367
-1
votes
2
answers
77
views
Question about epsilon and estimation Turing machines
i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
- 1
-1
votes
1
answer
675
views
Use Rice's theorem to prove the following is undecidable
Given the language $L=\{\alpha \mid M_{\alpha}(x)=x^3$ for all $x\in\{0,1\}^*\}$. Prove using Rice's theorem that $L$ is undecidable.
Rice's theorem: Let $P$ be a set of all computable functions $f:\...
- 263
-1
votes
4
answers
497
views
Relationship between an NP-hard problems with the subsets of them?
I am writing a paper. I have a problem and I want to prove that it is an NP-hard problem. However, for simplicity, I select a subset from my problem to prove that it is an NP-hard problem. Although I ...
- 37
-2
votes
3
answers
375
views
Is it $\mathsf{NP}$-hard to decide whether $\mathsf{P}=\mathsf{NP}$?
Is it $\mathsf{NP}$-hard to decide whether $\mathsf{P}=\mathsf{NP}$ ?
If so, what are the implications ? Is there result suggesting that it is the case ?
- 283
-2
votes
3
answers
2k
views
Does reachability belong to P?
Reachability is defined as follows:
a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?
Is it possible to write a polynomial time algorithm for it?
...
- 2,173
-2
votes
3
answers
1k
views
Is every problem in NP solvable?
Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
Charlie
-2
votes
2
answers
933
views
proving $P \subseteq PCP(0,O(log(n))$
I was working on proving this one and I've solve one direction as follows :
to prove that $P \subseteq PCP(0,logn)$ I said :
let $M$ be deterministic polynomial TM that accepts $L \in P$ ,we want to ...
-2
votes
2
answers
345
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 ...
- 211
-2
votes
1
answer
261
views
Show that the complements of NP-languages with one word per length are in NP as well
Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below.
L is in NP and
for every n, there is exactly one string of length n that belongs to
...
-2
votes
1
answer
1k
views
Which of these problems is not in NP? [closed]
I see one solved ex on Algorithms.
Which of the following is in NP?
Decision Version of TSP
Array is Sorted?
Finding the maximum flow network
Decision version of 0/1 knapsack?
...
- 139
-2
votes
1
answer
2k
views
3SAT to CNF-SAT reduction
I am trying to prove that 3SAT is polynome time reducable to CNF-SAT, but I don't know how to do this. A formula F is in 3SAT iff f(F) is in KNFSAT, but since 3SAT is a part of KNFSAT, every formula ...
- 409
-2
votes
1
answer
1k
views
-2
votes
1
answer
2k
views
What is the fastest known algorithm for matrix multiplication as of (2017/11)?
Recently I have learned about both the Strassen algorithm and the Coppersmith–Winograd algorithm (independently), according to the material I've used the latter is the "asymptotically fastest known ...
user76755
-2
votes
1
answer
76
views
What NP-complete problem to reduce to k-Edge-Colorability to prove its NP-hardness?
What known NP-complete problem would one reduce to $k$-Edge-Colorability to prove that the latter is NP-hard?
-2
votes
2
answers
146
views
A (False) Proof That ℙ≠ℕℙ
Why the following proof is invaid?
Using C-like pseudo-program:
Definition: bool S(Func, UInt): S(f,n)==true iff ∃x, x<=n, F(x)==true
F is defined in ℙ as a certificate function, so S is in ℕℙ.
...
- 3