Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,255
questions
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 ...
