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
1 answer

N vs NP. Existence or Constructive.

I was discussing P vs NP problem with somebody who works in computer science. I work in mathematics and know very little about computer science. My opponent told me, if you solve P vs NP problem, keep the solution to yourself, so you can crack…
Durian
  • 11
1
vote
1 answer

Complexity of a recursive function

I have a recursive function, and I'm trying to figure out it's complexity. denote P(n) - the runtime of the function (when given the parameter n). I know that : P(n)=n+(n-1)*P(n-1) [p(1)=1] How can I express P(n) without using P(...) ?
Belgi
  • 23,150
1
vote
1 answer

Many-One Reductions vs Turing-Reductions and PH

One definition of $\mathsf{PH}$ uses Oracles and in this definition both $\mathsf{NP}$ and $\mathsf{coNP}$ are contained in P^NP which equals $\mathsf{P^{coNP}}$. It is believed that $\mathsf{NP}$ does not equal $\mathsf{coNP}$, in other words they…
user427228
1
vote
0 answers

Find a simple Theta bound for a geometric series

I'm working on a question like: find a simple g(n) (big theta) for $ f(n) = \sum _{i=1}^n 5^i $ My working starts with this $\frac{5-5^n}{1-5}$ which is not equivalent to the correct answer from wolfram alpha: $\frac{5}{4}\left(5^n-1\right)$.…
Charlie Egan
  • 161
1
vote
1 answer

Implication of P =NP on video games?

I was wondering if NP problems were actually solvable in P time, then what will be the impact on Video Games, if any ?
Devey Singh
  • 27
1
vote
2 answers

exponential time complexity

given that: $f(n) = a^n$ and $g(n) = b^n$ where, a,b are positive integers and n is a positive real number does there exist some $f(n) \notin \mathcal{O}g(n)$? ie. $f(n) \leq c_1 \cdot g(n)$ is false?
Gus Kenny
  • 639
1
vote
1 answer

Is this minimization problem NP-hard?

Given an $m*n$ positive matrix $\mathbf{A}$ and an integer $K$, where $0
user111604
  • 11
1
vote
2 answers

Need help with a problem with algorithmic complexity

Is $n^2 = O(n^3)?$ Is that true? How does one go about proving it. If that's true, one can say that the time complexity of Bubble Sort is $O(n^3)$.
Saka Naka
  • 11
1
vote
1 answer

Computation Complexity polyL ⊆ QP, polyL ? P

Following Computation Complexity POLYLOGSPACE, Given that polyL / POLYLOGSPACE is the complexity class $⋃^∞_{=1}(()^)$, k is integer. QP / Quasi-polynomial is the complexity class , $⋃^∞_{c=1}TIME(2^{()^c})$, c is integer. (a) How to prove that,…
Peter HU
  • 141
1
vote
0 answers

Meta-Heuristic Algorithm

I have two-stage stochastic programming, including equations with high levels of complexity. The objective function is related to the first-stage variables and should be maximized. Also, one of the complex constraints is as follows: $$ P(i,j,s) =…
MTK
  • 11
1
vote
1 answer

Complexity of $T\left( n\right) =T\left( \dfrac{n}{3}\right) +T\left( \dfrac{2n}{3}\right) +\theta \left( 1 \right)$ without using master theorem

Calculate the complexity of $T\left( n\right) =T\left( \dfrac{n}{3}\right) +T\left( \dfrac{2n}{3}\right) +\theta \left( 1 \right)$ Without using the master theorem. My take on this: I found that the answer should be $\theta \left( n \right)$ but I…
GreekMustard
  • 147
  • 8
1
vote
0 answers

Given two problems, is it always possible to reduce one of them to another?

Suppose we are given two problems $A$ and $B$ (both are solvable). Is it always possible to transform one of it to another? That means whether holds $A \preceq B, B \preceq A, or A \equiv B$. This should be possible, if $A$ and $B$ are NP problems,…
El Sablo
  • 11
1
vote
1 answer

Computational complexity of $e^n$ which is $O(e^n)$, vs. $2^n$ which is $O(2^n)$

Is the Big-O of $e^n$ greater than the Big-O of $2^n$? I understand: We have a single time complexity class of exponential for $2^n$, $e^n$ and $4^n$ (if I am not wrong.) There is no real algorithm with $e^n$ complexity (if I am not wrong), so I am…
Mojtaba Mohammadi
  • 45
1
vote
1 answer

Show that $TIME(\sqrt{n})$ = $TIME(1)$

Also known as CMU 15-455, Spring 2017, Homework 2.4. Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$O$ and time complexity class $TIME(t(n))$. Definition: Let $f$ and $g$ be functions…
Bedivere
  • 81
1
vote
1 answer

Time complexity of Vieta's formulas

I need to find the time complexity for calculating the coefficients of the polynomial of degree $n$, if given it's roots. That is, if for $P(x)=(x-r_1)(x-r_2)...(x-r_n)=\sum_{i=0}^{n}a_nx^n$, values of $r_1, r_2,..., r_n$ are given, find $a_k$, for…
Đumić Branislav
  • 295
1 2 3
…
22 23