# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,201 questions
Filter by
Sorted by
Tagged with
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 ...
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?
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 ...
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 ...
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) ...
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 ...
21 views

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

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=...
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 ...
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 ...
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
74 views

• 335
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
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.
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
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 ...
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
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$ ...
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 ...
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 ...
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^* \}$
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 ...
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
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
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
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 ...