Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

Computational complexity is a part of theoretical computer science that answers questions about how efficient an algorithm is:

  • How much time (as a function of the size of the input) does the algorithm take to produce its output?
  • How much space (such as computer memory) does it require?
  • How much of some other resource does it consume? (For example, this can be the size of a logic circuit solving the problem, or the number of bits of randomness used by a probabilistic algorithm.)

We can similarly ask about the computational complexity of any algorithm that solves a given problem.

Often, very specific details of these answers (such as constant factors or additive terms) depend on specific details such as the computer you're using. To help deal with this, we often stick to determining the asymptotic complexity of an algorithm: see for more details.

A major problem in computational complexity is the P versus NP problem, which asks if a certain class of problems can be solved by an algorithm that runs in a number of steps that's a polynomial function of the input size.

3433 questions
0
votes
1 answer

Notion of circuit width seems to have little to do with memory.

As suggested in the title, I'm unhappy with the notion of circuit width I've been given in my computational complexity class. It was motivated as a model of amount of memory needed for the algorithm, but seems to me to be an arbitrary…
Zerkoff
  • 489
0
votes
1 answer

Proving lower bound for fibonacci sequence

Im trying to prove the lower bound for the following recurrance relation: $$ T(n) = T(n-1) + T(n-2) + O(1) $$ The question asks to prove $\Omega(k^n)$ for some $k>0$, using a recurrance tree. However I am confused, because it is impossible if $k$ is…
QOTDIANA
  • 5
0
votes
0 answers

Set cover problem aproximate solution NP-hardness

I need to prove that for some $\epsilon$ the approximate solution of Set Cover Problem with precision $\epsilon$ is an NP-hard problem. Can I present this problem as a VERTEX-COVER problem and then reduce MIN-3SAT to VERTEX-COVER and show that for…
reimash
  • 1
0
votes
1 answer

How to set this big O statement to get the results in the article?

In this article: https://arxiv.org/pdf/1603.05346v2.pdf, in page 3, when setting the K they suggested, I did not managed to get their results. This is the point: What I did in the meantime: What to do next?
igal leikin
  • 41
0
votes
1 answer

Asymptotic upper and lower bound for $T(n)=T(n-2)+\log n$

I'm trying to find the asymptotic upper and lower bound for $$T(n)=\begin{cases}0& n<2\\ T(n-2)+\log(n) &n\geq2\end{cases}$$ it follows that $T(n-2)=T(n-4)+\log(n-2)$, and therefore for $n\geq…
jeb2
  • 645
  • 4
  • 15
0
votes
0 answers

Given a poly(log(G), log(x)) algorithm and N>G, is it also poly(log(N), log(x))?

I have constructed an algorithm that runs in poly(log(G), log(x)). I am now asked to construct one that runs in poly(log(N), log(x)), where N>G. What would make the first algorithm not also run in poly(log(N), log(x))? (is the fact that N>G not…
Anon
  • 1,757
0
votes
0 answers

There exists a TM $M$ such that both $L(M)$ and $L\left(M_{\star}\right)$ are NP-Hard

I need to prove the following : Assume the $P\ne NP$ There exists a TM $M$ such that both $L(M)$ and $L\left(M_{\star}\right)$ are NP-Hard. let $L\left(M_{\star}\right)$ be the TM obtained from $M$ by swapping the accept and reject states.
Robert Piterson
  • 41
0
votes
0 answers

A computational complexity problem

Consider $n$ arbitrary (but fixed) unit-norm vectors $\mathbf{x}_1,\ldots,\mathbf{x}_n$ in, say, $\mathbb{R}^d$. Let $\beta>0$ be fixed. For $\mathbf{y}\in\mathbb{R}^d$, define the binary quantities $b_i = \mathbf{1}(|\langle…
Lord Soth
  • 7,750
  • 20
  • 37
0
votes
1 answer

For any arbitrary Turing machine, it will always decide a specific language $L$?

Is it true that every Turing machine $M$ will have at least 1 language $L$ such that $M$ decides $L$? I have been toiling really hard and I have still not found a Turing machine that will decide zero language. So, I just assumed it to be true.
Smit Patel
  • 3
0
votes
1 answer

need help finding time complexity of this loop

What is the time complexity of the following algorithm? SUMAB (A, B, N) sum = 0 for j = 1.. N k = 2 while k
hacker_panda
  • 15
0
votes
1 answer

Finding $n_0$ such that $2^{cn}>n^{2}\, \forall n\geq n_0$

Let $h(n) = n^{2}$, $c=1$ and $f(n)=2^{cn}$. find an integer $n_0$ such that $f(n) > h(n)\, \forall\,n\geq n_0$. I know that $n_0=4$ and I can prove it using induction, but is there a method to find such $n_0$? I tried doing inequalities such as…
tectonic
  • 3
  • 2
0
votes
1 answer

Definition of $coNP$

I have this question about the definition of $coNP$ in our lecture that I simply cannot wrap my head around. We define $$ coNP := \{L \subset \{0,1\}^* \mid \bar{L} \in NP\},$$ and then later on we give as an example $\bar{SAT} = \{\varphi \mid…
0CT0
  • 140
0
votes
1 answer

Finding average-case time complexity

I have an integer array and some x integer number. I'm looping through this array and compare each element with x, if there exists the exact element, the algorithm ends. The best case is B(n) = 1, the worst is W(n) = n. How should I count the…
khernik
  • 1,369
0
votes
0 answers

Proof of an alternative description of NP by a lemma

Consider the this lemma: The following two statements are equivalent for every set of M. $M \in NP$ there is a $N \in P$ and a polynomial q, that $M = \{x \vert \exists y, \vert y \vert \le q(\vert x \vert) : \in N\}$ (where $\vert x \vert$…
jri
  • 109
0
votes
1 answer

Sketch a proof that stCONN is in the class NSPACE(log n) = NL .

Given a graph G as input stCONN is the problem of determining if there is a path from start vertex s to target vertex t. Sketch a proof that stCONN is in the class NSPACE(log n) = NL. Can somebody please explain this to me as simply as possible? I…
Benny
  • 29
1 2 3
…
22 23