Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
2
votes
1answer
38 views

Transitions of Turing machine in Cook Levin theorem proof

I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing ...
1
vote
1answer
28 views

What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Given the following language: $$ L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
0
votes
0answers
32 views

Check if the given satisfying assignment of CNF formula is lexicographically the first

If there is a CNF Boolean formula in $n$ variables then the potential satisfying assignments are the binary strings of length $n$. Given a CNF Boolean formula and a satisfying assignment how ...
0
votes
1answer
39 views

Computational Complexity of an 'equivalent' 3SAT instance problem

Given a random $3SAT$ instance $(S_0)$ with $C_0$ clauses, $I_0$ variables. Objective: For any given value $C_1$ ($C_1<C_0$), create an 'equivalent' $3SAT$ instance $(S_1)$ with $I_0$ variables, $...
0
votes
0answers
38 views

master theorem `case 3` counter example? [duplicate]

as far as i understood from the proof of the master theory in the introduction to algorithms book while proofing the third case we assumed that $af(n/b) ≤ cf(n)$ ...
-1
votes
1answer
60 views

Quasilinear time algorithm for 3-SAT

Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?
0
votes
0answers
28 views

Is it possible to build a linear bound automata that decides A(NFA)?

Is it possible to build a linear bound automata that decides A(NFA)? A(NFA)=Accepting Non deterministic Automata - language that contains the encoding of all the NFAs together with the strings that ...
2
votes
1answer
50 views

What is an O(n)-approximation?

I see the following notations used: $O(1)$-approximation $O(n)$-approximation $\Omega(n)$-approximation Can someone please explain what they mean? I know what an approximation is with a normal ...
0
votes
1answer
26 views

Finding the homomorphism between two homomorphic graphs: what is the name of this problem?

The "graph homomorphism problem" can be stated as: given two graphs $G$ and $H$, determine if there exists a homomorphism $f$ such that $f: G \rightarrow H$. This is a famous problem that is ...
3
votes
0answers
35 views

Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...
1
vote
0answers
17 views

Complexity classes and "local pre-processing"

My question I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...
0
votes
1answer
40 views

What is wrong with this "proof" of $coNP = NP$? [duplicate]

I am wondering why the following "proof" of $coNP = NP$ does not work: $\subseteq:$Let $L$ be a language in $coNP$, that means there is a non-deterministic Turing Machine $M$ that decides ...
0
votes
1answer
31 views

Is it true that $P = coNP$?

I have recently read the definition of $coNP := \{L \ \mid \ \overline{L} \in P\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an ...
1
vote
1answer
33 views

Determine the time complexity of this algoritm (pseudocode)

{ t <- n while t>1 do t <- log_2(t) } I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\...
3
votes
1answer
35 views

Decidable languages unconditionally not in P/poly

What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones? I'm interested in unconditional results rather than examples such as the Karp–Lipton ...
0
votes
1answer
50 views

Reduction of RE and Rec languages

Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC. And also I know that if $...
0
votes
1answer
52 views

Prove Permutation approach of finding best paranthesization to matrix chain multiplication is $4^n$

Suppose we have matrices $A_0,⋯,A_{n−1}$ (you can say $n $ matrices). Matrix $A_i$ is with dimension $d_i\times d_{i+1}$. If we would like to find all possible permutations to find the best ...
1
vote
1answer
65 views

Is this divide-and-conquer algorithm O(n)?

Yesterday I came up with a divide-and-conquer algorithm about all subarrays of length k of an array of length n. Outline: ...
0
votes
2answers
39 views

Can you help me provide some examples of 3-co-SAT?

Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable, namely ...
4
votes
1answer
29 views

Attempting to verify the colorability using Wigderson's Algorithm

The algorithm of Wigderson (see here) can color a graph that is known to be $3$-colorable in $O\left( \sqrt{\left| V \right|} \right)$ colors. This is done in $O\left( |V| + |E|\right)$ time. For ...
2
votes
1answer
79 views

Currently best approximation for graph coloring

As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation ...
0
votes
0answers
12 views

Need literature on First order logic definibility through Automata

Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
1
vote
1answer
36 views

Difference between BPP, IP and AM complexity?

I just can't figure out the difference between these three classes of complexity, does anyone know the difference and can explain it in a simple, direct way without too many definitions involved? ...
1
vote
1answer
181 views

NP-completeness of satisfiability of formula over 50 variables

Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?
1
vote
1answer
39 views

In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?

This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result ...
1
vote
1answer
71 views

Is there a problem that had exponential time complexity but later was proven to be solvable in polynomial time?

Pretty much the title. I watched a video talking about P vs NP and it mentioned that the event that sparked this entire debate was the fact that some exponential time problems were shown to be ...
1
vote
1answer
51 views

Does $\mathcal{P}\neq \mathcal{NP}$ preclude the possibility that an NPC problem could have polynomial time algorithms on *almost* any input?

I do not have too much background in complexity theory, so please feel free to let know if my question is ill defined. My question is, does $\mathcal{P}\neq \mathcal{NP}$ preclude the possibility that ...
0
votes
0answers
25 views

Accessing Array-based vs LinkedList PriorityQueue

Question 1: Suppose we have the two priority queues, or we have two implementations available. One implementation uses an array to maintain the entries in the priority queue, while the other uses a ...
0
votes
0answers
49 views

Accurately determine the real 'hardness' value of any given input instance for subset sum

Assuming the 'hardness' of any possible input instance with $N$ elements (of any bit length) for the subset sum problem could be represented as $H \in \{0,0.000001,0.000002 \dots, 1 \}$, being ${0}$ ...
0
votes
1answer
25 views

How to show counting number of 1s in a binary word is under NC^2

A computational problem is said to be in the class $NC^K$, if the result $f(x)$ can be computed in time $O((\log |x|)^k )$ on a multi-processor computer, while the total number of operations remain ...
1
vote
1answer
20 views

The Turing Machine in the proof of Time Hierarchy Theorem

In the proof of the Time Hierarchy Theorem, Arora and Barak writes: Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
4
votes
1answer
644 views

Proofs of reduction of any hard problem

Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
0
votes
0answers
26 views

Given a graph and specific VC instance, find number of variables when reducing from VC to SAT

I have question already answered from past exam, and I'm trying to figure where my logic fails. Given a graph find vertex cover of size 2. The question is how many variables are there going to be for ...
3
votes
1answer
81 views

How hard is random SAT?

There is plenty of research into the so-called "random SAT" problem, where we basically try to solve SAT instances with clauses chosen "at random" in some sense. There are all ...
3
votes
0answers
22 views

Finding lattice points with fewest non-zero terms

Finding a short point on a lattice is hard, but I was wondering if finding a vector on the lattice which the fewest non-zero terms was easier? Are there any good approximations like LLL, but which ...
1
vote
1answer
55 views

What is the Runtime of this recursive algorithm?

I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
2
votes
2answers
178 views

Complexity of a variant of Subset Sum problem

This is the variant of SSP: Given $n$ positive integer points $a_1, \ldots, a_n$ which are all at most $n$, does there exist a subset $\{a_i\}_{i \in P}$, such that its summation is exactly $n+1$? My ...
0
votes
0answers
7 views

Are Path-systems P-complete under logspace many-one reductions?

As far as I know, the admissability of a path-system is an example of a P-complete problem. However, I am not sure under which kind of reductions (many-one or turing-reductions? logspace or AC$^0$ ...
0
votes
1answer
38 views

If $A\leq_P B$ and $B\in \text{NP}$, is $A\in \text{NP}$?

Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$. My question is, if $A\leq_P B$ and $B\in \...
2
votes
1answer
82 views

If P!=NP, does there exist infinite hierarchy of languages between P & NP?

This looks to me as some tweaking or generalization of Ladner's result on NP-I languages, can some help me in the right direction? or redirect me to some sources where this generalization is ...
0
votes
2answers
67 views

Does there exist a language O such that $NL^O= Dtime(n^{logn})^O$? How to proceed with the proof in either case?

I do have some intuition(although I would like to be corrected) regarding why $NL!=Dtime(n^{log n})$ as for some $L \in Dtime(n^{log n})$ it might be required for the TM deciding it to read inputs of ...
1
vote
0answers
61 views

Square of a directed graph $G=\left< V, E\right>$

I have this question from CLRS book please. Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2 $ iff for some ...
1
vote
1answer
185 views

What is the regular expression for the language, {w | w does not contain the substring 11}

{w | w does not contain the substring 11} What I am thinking: $(0^* 1 0^* )^*$ Is anything wrong with my expression? Thanks in advance for your help!
1
vote
1answer
87 views

One-tape Turing machine for doubling words (strings)

I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape ...
1
vote
1answer
26 views

Finding maximum clique given, for each edge, union of all cliques containing it

For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$. Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
0
votes
0answers
17 views

Where does this Oracle Problem belong in the Polynomial Hierarchy?

Given a problem $E_0$ such that: Any valid solution $S_0$ if there is any is of polynomial length. Assuming we are able to guess the solution $S_0$, for it to be valid: i. There are a fixed set of ...
0
votes
0answers
17 views

A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining

I would to discuss a proof found in CLRS book please. Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...
3
votes
0answers
66 views

3SAT to 1-in-3SAT reduction with additonal constraints [closed]

The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows: For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables ${a,b,c,d}$ and replace original clause with below 3 clauses: $R(x−,a,...
1
vote
0answers
33 views

NP-hardness proof of an optimization problem with real values and real input in the decision problem

Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
1
vote
0answers
36 views

Approximation classes for optimization problems with real values

Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.? If my understanding is correct a ...

1 2
3
4 5
95