Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,750 questions
Filter by
Sorted by
Tagged with
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 ...
125 views

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\... 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 ... 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 ... 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$| ... 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$. ... 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 ... 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 ... 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 ... 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 =... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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? 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 ... 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 ... 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$... 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 ... 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 ... 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 $$\... 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,... 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 ... 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 ... 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 ... 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 ... 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(... 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(... 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 ... 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 ... 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), ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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! 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 ... 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: ... 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}...
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, ...