# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,255 questions
Filter by
Sorted by
Tagged with
24 views

### Implications in $\mathbb{NP}$-completeness

Suppose I have an $\mathbb{NP}$-Complete problem called problem $A$. Further, suppose that $A$ is poly-time solvable in undirected-acyclic graphs; in other words, trees. Now, If I take a problem ...
15 views

### Configuration of a space bounded turing machine

A configuration of a Turing machine is defined as the following: an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string on the tape, $q$ denotes the machine's current state, and $k$...
93 views

### Proving that whether a Linear Bounded Automaton runs in polynomial time or not is undecidable

How would one prove that whether a Linearly Bounded Automaton (i.e a Turing Machine where the number of tape cells you can visit is not infinite but is bounded by the size of the input, i.e if the ...
15 views

### single circuit simulating multiple Turing machines

You can simulate polynomial time Turing machines with polynomial size circuits, can you simulate multiple poly time TMs with a single poly size circuit?
14 views

### Simulation of circuits with circuits

From classical results of universal simulation of Turing machines there exists a Universal Turing machine simulating any Turing machine with time complexity 𝑇(𝑛) in time 𝑇(𝑛)log𝑇(𝑛). Is there is ...
33 views

### Create a turing machine for log base 2 of n

How would someone create a Turing machine that computes ⌈log2(n)⌉? I know that: n = 1, 2, 3, 4, 5, 6, 7, 8, ... f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ... And that I want the input tape to have n 1's in it to ...
35 views

### Recurrence relation $T(n/10) + T(c·n) + n$

Given the following question: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure) ...
26 views

### Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?

I thought they did, but recently I tried to express $3^n$ as $k \times 2^n + o(2^n)$ for some constant $k$ but wasn't able to. All I found was $3^n = (\frac{3}{2})^n 2^n$. What am I misunderstanding ...
39 views

35 views

### If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?

In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds? i take as granted that both of f(n)=o(h(n))...
22 views

### Definition of BPP

We know that BPP is described as $\{L\mid \exists \text{ TM }M, \text{ s.t. }\Pr[M(x)=L(x)]\geq2/3\}$. I saw a proof which uses Chernoff bound to prove that any probability larger than $1/2$ can be ...
23 views

### How to explain that a program that runs in NTIME(O(lg n)) is in the class P?

if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that ...
13 views

### Is undecidability contained in $PSPACE / o(exp(n))$?

It is not hard to show that $DSPACE(n+1)/2^n$ contains undecidability. But is it possible to make the advice string subexponentially long (while the machine is allowed to have any $poly(n)$ space) ...
20 views

### Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)

Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The ...
29 views

### Searching for an algorithm with $\Theta(n2^n)$ time complexity

I am searching for an algorithm with a time complexity of $\Theta(n2^n)$ time complexity. I am aware, that e.g. the Fibonacci sequence has a time complexity of $\Theta(2^n)$. My plan was to add a loop ...
69 views

### Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?

Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but ...
25 views

### If $f(n)=n^a$ for a given $a>0$, find $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$

If $f(n)=n^a$ for a given $a>0$, I need to find a function $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$. I am not sure how to find such function, which satisfies both of the ...
16 views

### For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$?

Let $L$ be an $\mathrm{NP}$ language. Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{*}$, $x \in L$ if and only if ...
23 views

### Complexity class of problem whose running time features binomial coefficient

I've built an algorithm that, starting from an array of $n$ cells and an integer value $s$, builds $\binom{n+s-1}{s}$ vectors (that is, all the ways to add a certain $s$ quantity fully distributed ...
35 views

### 1-OR-3-SAT is in P

1-OR-3-SAT: Input: 3-CNF formula $\varphi$ Question: whether there is an assignment $x$ such that in each clause there are one or three true literals. I need to show that this problem is in $P$. I ...
26 views

### Reduce Subset-Sum to Sat

Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers. SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn }...
30 views

### Complexity of a decision problem: system of linear equations over finite field with restricted solutions

I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
23 views

### Showing resolution algorithm for 2SAT is polynomial time

I don't quite understand why the resolution algorithm completes in polynomial time for 2SAT but not 3SAT. I'm looking at slide 42 of these slides for reference. It is clear that given two clauses of ...
47 views

### Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third

I have found this answer that finds the center of an input string in nlog(n) complexity. I have tried to use it as a starting point to find an algorithm that finds the character(s) that separate the ...
33 views

### Solve recursive function $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$

In one of my college assignments, I came up with the following recursive function which I'm asked to solve: $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$ I tried a change of the variable or the ...
35 views

### Is this a hitting set or set cover problem? [closed]

Define a universe $U$ containing $N$ elements. We are given $N$ sets, each of which is a set. For example, $U = \{1, 2, 3, 4\}$ and sets \begin{align} S_1 &= \{\{1\}, \{2, 4\}\}, \\ S_2 &= \{\{...
28 views

### Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

in one of my college assignments i came up with the following recursive function which I'm ask to solve: $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$ I could not use master method on it and it ...
61 views

### Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?

Example: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $O(\log_t n)$ (where $t \in \mathbb{N}$ is the order of the tree). There was one true/false question on ...
17 views

### Are regular grammar languages defined from “accepting” states?

In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
I came across this symbol $2^{\mathcal{O} (n)}$ and I can't figure out what is means. What complexity class is this?