# complexity-theory's questions - English 1answer

3.205 complexity-theory questions.

### 1 Deleting edges such that largest connected component has at most $n/4$ nodes

1 answers, 47 views complexity-theory graphs
Let $G = (V, E)$ be a connected undirected graph with $v > 6$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $n$ edges. Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific ...

### Modify max value multiple times of a list

1 answers, 47 views algorithms complexity-theory
I have two lists say $A$ and $B$, each consisting of n positive integers. I make a list $C$ such that each element of $C$ i.e., $C_i=A_iB_i$ for each element $A_i \in A$ and $B_i \in B$. Now I have ...

### 2 Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...

### 3 Show that NP is closed under concatenation

2 answers, 2.047 views complexity-theory closure-properties np
Show that NP is closed under concatenation. This is a homework problem and I would appreciate some guidance. I began by saying the following: Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be ...

### Regarding time complexity of multi-tape Turing machines

1 answers, 11 views complexity-theory turing-machines
So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM? I just don't know where to get started...

### 6 Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.

### 1 For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

1 answers, 34 views complexity-theory 2-sat
For which $c, d$ is $Gap2SAT[c, d]$ in $P$ (such that $0<c<d<1$)? (I know if d=1 then for each c it will be in P, however with which c,d such that $0<c<d<1$ can I simply return ...

### 2 Why is SAT in NP?

I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?

### 2SAT Problem using Implication Graph

I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each ...

### 1 provably optimal search algorithms?

1 answers, 48 views complexity-theory search-algorithms
In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-...

### Minimal hashing function for integers that satisfy specific constraints

I'm looking for a kind of way to create a minimal perfect hash function given a set known integers. More specifically, I have M numbers within the range 0-N with N > M. Does it exist a way to create ...

### Find asymptotic bounds $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$

Give the recurrence relation: $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$ ($k$ is some constant and assume $n$ is $2^t$ for some $t\in \mathbb{Z}$) I'm trying to ...

### 1 reducing a decision problem to a local search problem

Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states: If a PLS problem is NP-hard then NP = P So assuming L is a PLS problem (polynomial local search problem) that ...

### 2 Complexity of nearest codeword in cyclic codes

1 answers, 31 views complexity-theory coding-theory
Is it $NP$-complete given $c(x),g(x)\in\mathbb{F}_2[x]$ where $g$ generates a cyclic code of length $n$ (so $g\mid x^n-1$), and $\deg c<n$ to find the nearest codeword to $c$? This is related to ...

### 2 Card dealing problem with constraints (blacklisting),

A friend of mine and I are trying to teach a bot play a card game (bela) We are using monte carlo tree search (MCTS) to estimate the probability of winning hand in regards to multiple possible (!...

### Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference

Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A). I know that ...

### Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

The Problem: I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set: ...

### Quick search of objects based on distances

0 answers, 17 views complexity-theory search
I have some objects $x\in X$ and a metric $s:X\times X\to\mathbb{R_{+}}$. For each $x$, there is a $y\in Y$. Note that $x$ and $y$ are highly structured and we cannot consider neural networks for ...

### 1 What is the real reason that Bubble Sort runs at O(n) in best case?

In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...

### Checking if the clauses are satisfiable

0 answers, 27 views complexity-theory satisfiability 3-sat
I want to test if this clause: {x,y,z},{¬x,y},{¬y},{¬z} is satisfiable. However, I noticed that the clauses contain more than two literals. How can I check whether the formula is satisfiable. So ...

### 5 Have any natural complexity classes been proven not to be closed under complement?

Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be? I'm sure one could construct some contrived ...

### Using Implication Graph to check 2-Satisfiability

I have the following boolean formula: {x,y},{-x,-y},{x,-y}, and below is the corresponding Implication graph: I know that the next step is to check for 'bad loops'/Strongly Connected Components. ...

### 1 Drawing an implication graph for 2-SAT clauses

1 answers, 3.896 views complexity-theory logic satisfiability
I am trying to convert the following 2-sat clauses to implications and then draw the implication graph. The clauses are: ...

### Understanding the logic of algorithm runtime

I'm trying to understand the runtime of this code:def f(n): if (n <= 1): return 1 else return f(n-1)*f(n-1) + f(n-1) At first, my logic said ...

### 2 Is SAT known to be non-context-free or even non-regular?

We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas. Has something similar been done for SAT?

### 4 Are there any optimization problems in P whose decision version is hard?

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...

### How to prove that this TSP variation is NP-Hard?

The problem is as follows: given a list of cities, a list of distances between them, and upper bounds for date/times that the cities must have been visited by, compute the shortest (optimal) going ...