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

Prove in complexity theory

Given a language A, which is in NP and also not NP-complete, I have to prove that P != NP. [Note: A is not trivial] Any suggestions?
Asaf Kahlon
  • 1
0
votes
2 answers

Multiplying Big-Os

I've seen the following in a text: $\mathcal{O}(\sqrt{n})\cdot \mathcal{O}(n\log n)$ How is that even defined? Ok, I guess one can replace it with: $\mathcal{O}(\sqrt{n} \, n\log n)$ Is that right?
Ystar
  • 2,866
0
votes
1 answer

Find subset sum problem verifier and its complexity

As homework we need to find a P-verifier for the subset sum problem. Given: natural numbers $a_1, \cdots, a_n$ and $b$ Output: YES if there is a subset $S \subseteq \{a_1,\cdots,a_n\}$ where $\sum_{a \in S} = b$. NO otherwise. My idea: There is a…
Chris
  • 521
0
votes
1 answer

Prove non-equivalence with Big Omega

How to prove non-equivalence of this? $a^n = \Omega(b^n)$ when $0 < a < b$
Ondrej Janacek
  • 179
0
votes
1 answer

Understanding the meaning of the Linear speedup

The linear speedup theorem informally says the following thing: If $M$ is a Turing machine that operates with time $f(n)$ to do a certain task on some input $x$ then for every $\epsilon>0$ we can construct another Turing machine that operates on…
Dubious
  • 13,350
  • 12
  • 53
  • 142
0
votes
0 answers

3-SAT vs P/poly

Why is the circuit for a 3-SAT instance not polynomial in size? That is, when I am converting a SAT formula into a circuit, isn't the size of the circuit polynomial, as I have polynomial number of clauses?
user134037
  • 1
0
votes
1 answer

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^\frac{1+\sin(\frac{n\pi}{2})}{2}$ and $g(n) = \sqrt{n}$.

Find whether $f(n) = O(g(n))$, $f(n) = \Omega(g(n))$ or $f(n) = \Theta(g(n))$ if $f(n) = n^{\big(\displaystyle 1+\sin({n\pi}/{2})\big)/2}$ and $g(n) = \sqrt{n}$. I tried plotting this out - it oscillates, and the exponential is $0 \le x \le 1$...…
Gabba
  • 1
0
votes
1 answer

How to prove $n^2$ is not in $n^3$

How would I go about to prove the simple complexity of $n^2$ is not in O($n^3$)? Also , how would I go about doing this for big Omega and Theta? Ex. Prove $n^4$ is not in Omega(n^3)??
user3325924
  • 3
0
votes
2 answers

Why can you find a $k$-clique in polynomial time, but determining if there is a $k$-clique is NP-complete?

You can find a $k$-clique in $n^k$ time by examining all possible sets of vertices of size $k$. So why is it NP-complete to determine if there is a clique of size greater than $k$? It looks like you can solve it in polynomial time if $k$ is a…
Jessica
  • 449
0
votes
1 answer

NP-hardness of an Integer Program

Could someone please explain if it has been proven that the following problem is NP-hard $$\mathrm{maximize}\sum x_i$$ $$A\mathbf x\leq1$$ $$x_i\in\{0,1\}\forall i$$ where $\mathbf x = (x_1,\dots,x_N)^T$, $A$ is a constant matrix and $x_i$ are…
triomphe
  • 3,848
0
votes
1 answer

Word-chain game complexity

There's a popular game, when two people each after each call cities in such a way that every next city begins with the previous one's last letter. For, example: A: Washington B: New Orleans A: Syndey B: York A: ... The first one who can't name…
Serge Seredenko
  • 380
0
votes
3 answers

Prove or disprove: $n\log ({2^n}\log ({n^2})) = O({n^2})$

Prove or disprove: $$n\log ({2^n}\log ({n^2})) = O({n^2})$$ What I reached so far is: $$\eqalign{ & n({\log _2}{2^n} + \log ({n^2})) = \cr & n(\log n + \log ({n^2})) = ? \cr} $$
Daniel Gagnon
  • 535
  • 3
  • 11
0
votes
1 answer

Time complexity comparison

I'm struggling with these 2 questions: What are the relations $(\mathcal O, \theta, \Omega)$ : $\quad\text{a.}\,$ $\log(n!),n\log(n)$ $\quad\text{b.}\,$ $\ln\left(e^{e^k}\right)^{\displaystyle\ln(\ln…
user109346
  • 1
0
votes
1 answer

Knapsack Problem And Computational Complexity

(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9} (ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, 3, 9, 81 } (essentially powers of 3) (iii) Is…
C'est Moi
  • 3
0
votes
1 answer

Computational complexity of Newtons Method

I'm trying to do a worst case complexity analsis of another algorithm that involves computing an nth root of a real number at each step. I have a bound B on the size of this number also n is fixed and I'm computing the nth root to fixed precision…
Socrates
  • 51
  • 2
1 2 3
…
22 23