Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
1
vote
0answers
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$...
0
votes
0answers
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 ...
0
votes
1answer
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?
1
vote
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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) ...
0
votes
1answer
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 ...
0
votes
0answers
39 views

Prove that $T(n)=\omega(n)$?

Edit: can someone provide clear answer with all details Given: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
0
votes
0answers
36 views

Since P-Uniform = P does NP-Uniform (is there such a thing?) = NP?

A circuit family is $P−Uniform$ if there exists a polynomial time $DTM$ which on an input of $1^n$ outputs the description of $Cn$, the $n$th circuit. Presumably $NP-Uniform$ would look something like ...
5
votes
2answers
806 views

Exact definition of average time complexity?

Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least. Here is a definition that I feel comfortable with: Consider ...
0
votes
2answers
46 views

Failing to solve a recurrence by induction

My question is strongly related to the one asked here: How do I show T(n) = 2T(n-1) + k is O(2^n)? $$T(n)=2T(n-1)+1$$ Going with the steps, I reached the point where: $$c*2^{n}\geq c*2^{n}+1$$ which ...
2
votes
2answers
59 views

proving that a problem is in P

I read online that this problem is in P: Problem = {a^n, where n is a primary number} I can't find any algorithm that decides if a word w in ...
2
votes
1answer
18 views

#perfectMatchings is self-reducible

How can one show that the counting problem: Given a graph, output the number of perfect matchings Is self reducible? I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics: ...
1
vote
1answer
35 views

What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?

How can an NDTM have a growing number of branches as you feed larger and larger inputs with only finite number of transition rules specified--ie what is the relationship between the number of branches ...
1
vote
1answer
18 views

Different Classes of NP

I was solving problems related to P and NP where I encountered the following problem: Given a standard definition of NP, if x belongs to L then there exists y such that |y| <= |x|^d and A(x, y) = ...
1
vote
1answer
28 views

Decidable language that has no finite description?

A language is a collection of strings--assuming we have an infinite number of words then concatenating this collection (keeping things simple, normally you need to at least be able to tell where one ...
1
vote
0answers
13 views

Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of ...
0
votes
0answers
33 views

$P$-Complete proof

I need to solve the next problem: Consider the language: $$\operatorname{LIN\mbox{−}PROG} = \left\{(A, b)\bigg|\begin{gather} \exists\in\mathbb{R}^n\ Ax\leq b\text{ where }A\in\mathbb{R}^{m\times n}\ ...
0
votes
1answer
14 views

Does $\{0, 1\}^*\in \text{co-NP}$?

There is trivially $\emptyset\in\text{NP}$. From the definition of $\text{co-NP} = \{L : \overline{L} \in \text{NP}\}$ where $\overline{L} = \{0, 1\}^*-L$ follows $\{0, 1\}^*\in \text{co-NP}$. Is this ...
0
votes
1answer
36 views

If A is not in NP, and A reduces to B, does this mean B is not in NP?

I know it is true that if A is not in P, and A reduces B, then B is not in P. But is it true for NP as well? If A is not in NP, and A reduces to B, does this mean B is not in NP? Why or why not? ...
7
votes
1answer
872 views

Is there a simple argument why graph isomorphism is not NP-complete?

I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete. I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of ...
-2
votes
0answers
12 views

Turing Machine Encoding Legth

Given a problem of Turing Machine, the problem specified the length of encoding turing machine as less than $n$. What are the things that can be inferred from the encoding length of turing machine in ...
0
votes
0answers
23 views

Good Articles/book on neural networks

I search good articles or books on neural network. unfortunately i don't a lot of time and only now i started to research this field. so i actually search a good source that will give the fundamental (...
0
votes
1answer
10 views

Approximation algorithms for an instance of the Monotone circuit satisfiability

I have the following problem. Given a below boolean formula (of the type explained below) containing $n$ literals and two parameter $k$ and $l$, come up with a satisfying assignment of literals such ...
0
votes
0answers
62 views

3-Sat reduction to facility location problem

I'm learning about NP problems and I this problem which is a bit challenging for me. You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges ...
1
vote
1answer
74 views

Connection between Pseudo random generators and hardness

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
0
votes
1answer
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))...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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) ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 }...
4
votes
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 &= \{\{...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
47 views

Question about complexity of algorithms

I came across this symbol $2^{\mathcal{O} (n)}$ and I can't figure out what is means. What complexity class is this?
0
votes
0answers
36 views

Are all reductions from NP-complete problems either NP-complete or are contained in P?

Let's say we have a problem $A \in \mathsf{NP}$. Now let's say we have a reduction $f(\mathsf{SAT}): A \leq \mathsf {SAT}$. So, assuming that $A$ is not $\mathsf{NP}$-complete we have that $f(\mathsf{...
2
votes
0answers
34 views

Circuit complexity of hardest monotone function

Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of ...

1
2 3 4 5
86