Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0
votes
2answers
104 views

Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
1
vote
2answers
125 views

Need the type of time complexity and its formula

If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence: At $n = 4$ the number of operations = $(n - 2)$, $n = 5$ the number of operations = $((n - 2) (n-2)(n-...
-4
votes
3answers
92 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
0
votes
1answer
42 views

Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
3
votes
1answer
110 views

Reduction from the SAT problem to the NAE-SAT problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
0
votes
1answer
38 views

Reduction from the Clique problem to the Odd Clique problem

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
33 views

Complications of a language that reaches a state of reject

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \...
1
vote
1answer
37 views

Language in NPC and CoNP

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. the question: given: $A \in NPC$ $A \in CoNP$ Determine which of the following statements is correct: $P\...
2
votes
2answers
162 views

tautology vs satisfiability

I had a test that I failed to pass, and it had a question that I failed to do. This is the question: Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
0
votes
1answer
74 views

Reduction from TSP to even TSP

I have a question from a test that I failed to pass, I failed to do the question. The question: Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight ...
1
vote
1answer
76 views

Complexity of the language that enters an infinite loop

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. This is the question Let's look at the language $L_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | ...
0
votes
3answers
59 views

Relationship between NP and CoNP

I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question This is the question Will be $A\in NP$ Suppose that $A\notin CoNP$. ...
1
vote
2answers
67 views

Reduction with CoNP and CoNPC

I have a question I was unable to do, from a last test I had. This is the question: Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$. Determine ...
1
vote
1answer
29 views

Reduction with NPH

I have a question in complexities that I could not do. There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$. Determine which of ...
-1
votes
1answer
40 views

Reduction from SAT to 3SAT

a few days ago I had a test and could not pass it. This is a question I did not understand in the test. Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
1
vote
2answers
183 views

Reduction from vertex-coloring problem to edge-coloring problem

A few days ago I had a test and could not pass it. This is a question I did not understand in the test. We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
0
votes
1answer
28 views

Complexity of the maximal minimum size problem

Here is a question that I do not understand: There is a list of items $E = e_1,\dots,e_m$. Suppose we have two players (the first and second). Each item $e_j$ has a value $v(e_j) \ge 0$. The values ...
0
votes
1answer
34 views

How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
2
votes
1answer
44 views

Why this problem is NP-Hard?

I'm asking about the question described here: Knapsack Problem with exact required item number constraint Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
0
votes
0answers
25 views

Is the name 'class' from 'Complexity class' came from ZF set theory?

I just want to know if people in the complexity initiated the name 'class' because the term 'class' in Zermelo-Fraenkel set theory or not? For me, I assume the answer is Yes; because it doesn't seem ...
3
votes
1answer
42 views

Show that $P^A \neq EXP^A$ for all oracles A

I knew that $P \neq EXP$ by Time Hierarchy Theorem. But, I'd like to show that $P^A \neq EXP^A$ for all oracles A. How can I do it? I knew that If I make A=EXP, PSPACE, NP, and many others, then this ...
2
votes
2answers
105 views

Satisfiable CNFs where each clause contains logarithmically many different literals

Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability. A side note before, to be more clear: A CNF clause consists of $n$ clauses ...
3
votes
1answer
62 views

FPT algorithm for Knapsack

I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?
1
vote
0answers
22 views

Research on exact-cover problem and graph theory for NP-complete problems? [closed]

Sorry for the vagueness, but I'm trying to study the latest progress on the exact cover problem and using graphs for NP-complete problems. Googling around has not been very helpful. I understand the ...
2
votes
0answers
54 views

A synctactic property of the complexity class P

In these lecture notes the authors mentions that P is a syntactic complexity class, as we can find a decidable set of encodings for all polynomial time Turing machines. Of course, given a ...
1
vote
2answers
87 views

"Polynomial Counter" Turing Machine

I need some help with this question: Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...
3
votes
1answer
107 views

Merging Tuples of Intervals

Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements ...
-6
votes
3answers
143 views

Why has it taken so long to prove that P != NP?

A question that answers itself. If P=NP could be proved in a formal language, then surely it would be as easy to verify the proof as it would be to discover/derive it? Couldn't a program just quickly ...
0
votes
1answer
46 views

Is this variation of Max-Coverage NP-hard?

Setup An instance of Max-Coverage is typically defined by a collection of $n$ sets $S = \{s_1, s_2, \dots, s_n\}$, and a budget $k$, where the objective is to select a subset $U\subset S$ such that $$\...
0
votes
1answer
17 views

Reduction from 2 finite languages when one doesn't include epsilon and the other does

Just did a test about the subject that had the following question: I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off. $L_2$={ab,$...
2
votes
1answer
53 views

Does Nondeterministic TM is a counterexample of Extended Church-Turing Thesis?

We know that Extended Church-Turing Thesis (or Cobham's thesis) states that any 'reasonable' model of computation can be equivalent to Turing Machine model in at most polynomial time overhead. People ...
3
votes
0answers
55 views

Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
2
votes
0answers
28 views

What was the original paper that showed a simulation of turing machines via circuits?

It is a very standard construction in most complexity theory courses to turn a turing machine into a circuit. I thought this was due to Cook, but it looks like he did the reduction to SAT not through ...
1
vote
1answer
21 views

Does this Qualify as Sub-Exponential?

I don't have a strong CS background so apologies if the question is trivially simple: So I am working on an algorithm, say $A(n)$ , which runs over all integer partitions of $n$. Now the algorithm ...
0
votes
1answer
45 views

Need help understanding tightest lower bound ( BigOmega ) of n!

I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
2
votes
1answer
49 views

Number of queries for $NP^{NP}$

So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(...
2
votes
1answer
64 views

Ask for help to prove a inequality, thanks

Can anyone help to prove that $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$? Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
0
votes
0answers
57 views

Calculate the Cyclomatic Complexity

Calculate the CC (Cyclomatic Complexity) of the following code snippets. I am not sure if I have drawn the Control Flow Graph correctly and furthermore if my calculation for the Cyclomatic Complexity ...
2
votes
1answer
67 views

Does MIP* = RE's major breakthrough mean quantum computers are more powerful than turing machines?

Henry Yuen's youtube comment on this video https://www.youtube.com/watch?v=HL7DEkXV_60 (should be one of the top comments) explains that with the help of quantum entanglement (or quantum computers), ...
2
votes
1answer
49 views

$\log n$ lower bound for space complexity

I am currently reading Arora and Barak's Computational complexity. In Chapter 4 (Space complexity), they say the following: Since the TM's work tapes are separated from its input tape, it makes sense ...
3
votes
1answer
36 views

Is there a $L$-complete variant of SAT?

Many complete problem of different class of complexity has SAT variant. Like 3-SAT or $k$-SAT is $NP$-complete, Horn-SAT is $P$-complete, 2-SAT is $NL$-complete, and so on. So I was wondering if there ...
1
vote
3answers
156 views

Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
0
votes
1answer
51 views

What will happen to LOGSPACE if P=PSPACE?

If P=PSPACE then by padding argument EXPTIME=EXPSPACE.But what about class L(Logarithmic space)?What will it be equal to?I can't think it as equal to DLOGTIME.There are problems that can be solved in ...
0
votes
1answer
29 views

Does the problem belong to NP class?

So I am studying for my Algorithm theory exam and this is the problem i could not solve: Given numbers $x_1, x_2, ..., x_n$ which are the sizes of $n$ files and disk capacity $D$. Determine if you ...
1
vote
1answer
29 views

Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters

I am looking for the computational complexity of the following problem. Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same ...
-2
votes
1answer
319 views

Construct a DFA which accepts all strings containing both 11 and 010 as substrings

I have drawn the DFA for language L1 containing 11 as substring and language L2 containing 010 as substring. But I don't know how to concatenate these two to get the final answer. Please help!
0
votes
0answers
37 views

Build a Turing machine to prove that a problem is $NL$

If we the language $A$, which is defined like this: $$A = \{\langle G,s,t \rangle \} \mid \text{ There is a maximum path in graph $G$ that begin in $s$} \} $$ I want to build a Turing Machine that ...
9
votes
2answers
332 views

What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive. So this leads to the question: ...
0
votes
1answer
91 views

Counting strongly connected components in a directed graph in $NL$

Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$ I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
1
vote
1answer
45 views

Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...

1
3 4
5
6 7
95