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
1
vote
2 answers

Dominating Big-O

How could I prove that $O(5^n)$ is dominated by $O(n!)$ by using induction? Or: $5^n \in O(n!)$ I've got the basic formulas written out in regards to $f(k+1)$ but I'm just not sure how to proceed.
user469948
1
vote
0 answers

Prove that for some size of circuit there exists function which requires some number of gates

Prove that for every function $s(n)$ such that $n≤s(n)≤\frac{2^n}{100n}$ there exists a Boolean function $f:{0,1}^n→{0,1}$ such that $f$ doesn't have a Boolean circuit of size $s(n)$ that computes it but has a Boolean circuit of size $10s(n)$…
user343207
1
vote
1 answer

Show NP is closed under "relabelling"

This is an interesting question I'm stuck with: Define a relabelling to be a function $\phi : \Sigma \to \Sigma$ (not necessarily a bijection). If $x = x_1 \ldots. x_n$ is a string, we define $\varphi(x) = \varphi(x_1)φ=\varphi(x_2) \ldots…
user417638
1
vote
1 answer

How do you prove that a sum of functions is in Omega of one of the functions?

I have to prove the following statement: $$ f(n) + g(n) \in \Omega(f(n)) $$ I am not sure what to do. Can I use this somehow? $$ f(n) \in \Omega(g(n)) : \iff 0 \le lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} < \infty $$ Thank you in advance for any…
user46317
  • 155
  • 4
1
vote
1 answer

Why is the halting language and its complement the only possible separating languages?

Earlier I asked similar questions, but I deleted it because I don't think it was clear. I was reading Computation Complexity by Papadimitriou, and as the book defines recursively inseparable languages, it says $H$ and $\overline{H}$ are examples of…
Ralff
  • 1,487
1
vote
1 answer

Why is it obvious that P is contained in PSPACE and NP contained in NPSPACE?

It seems that if an algorithm ran in polynomial time on a deterministic Turing machine it would not require more than polynomial space because it would basically take more than polynomial time to use up that much space. But really, I am not sure...
Ralff
  • 1,487
1
vote
1 answer

what is the time complexity of following code? $O(n^3) $or $O(n^4)$

What will be the time complexity of the following function? is it $O(n^3)$ or $O(n^4)$? i am getting $O(n^3)$ in the first for loop, it will undergo $n$ times. in the second for loop, for every nth element it will go $n^2$ times, therefore the total…
Kamal Pratap
  • 13
  • 3
1
vote
1 answer

Why Savitch's theorem doesn't prove that NL = L?

Savitch's theorem proves that PSPACE = NPSPACE. Why the same theorem doesn't prove that NL = L?
Rami
  • 481
1
vote
1 answer

Time complexity - Doubling the speed of a machine that uses a O(N Log N) algorithm

Related to this question: Time complexity - Why does doubling the speed give this improvement? If we can solve a problem of size $n = 10^6$ in 20 seconds, and then we double the machine speed, how big of a size problem can we now solve given a…
rawr rang
  • 213
1
vote
1 answer

Question about computational complexity of algorithm

I'm quite confused about something. *So I have an algorithm which takes as input $k!$ numbers, let's call them $x_1, x_2, \ldots, x_{k!}$. *Then, in the algorithm, a 'matrix' is defined: i.e. for each $i$ and $j$ ($i$ from $1$ to $k-1$, $j$ from…
Dorry
  • 13
1
vote
1 answer

Does decidable imply bounded complexity

Is there any such thing as a decidable problem that cannot be bounded in complexity by a function? Let L be the language of pairs of computable expressions/programs that would evaluate to the same value. Can this language be bounded? If the…
Ken
  • 347
1
vote
1 answer

Is an obviously-correct obviously-PTIME algorithm in a programming language a proof of polynomial time reduction?

This is about NP and NP-completeness. I want to prove that language $L_1$ is polynomial time reducible to $L_2$. If I describe both languages as two sets of strings and write a program or a function in a programming language that takes string $S_1$…
CrabMan
  • 1,123
  • 7
  • 16
1
vote
1 answer

Time complexity of optimization problem

Since I'm very new to complexity theory, I was hoping someone can give me some advices/hints on the following problem. Suppose we know the values of $x_i$, $i=1,2,3,...,n$. How do we choose an integer $k$ such that $\sum_{i=1}^{k} (k-n)x_i$ is…
Dan Neal
  • 53
1
vote
0 answers

Is there any example of real-life decidable problem that is not in EXP?

In order to illustrate an introduction on computational complexity, I am trying to find examples of real-life problems for every one of the main complexity classes: $P$, $NP$, $EXP$, $R$ and undecidable. The idea is to have at least one problem per…
FClad
  • 11
1
vote
1 answer

Describe a polynomial-time algorithm to compute the function expressed by the boolean formula

Let $\varphi$ be a boolean formula of $n$ variables and $(t_1, t_2,\ldots,t_n) \in \{0, 1\}$ be an assignment. How to describe a polynomial-time algorithm to compute $\varphi(t_1,t_2,\dots, t_n)$?
user272816
1 2 3
…
22 23