Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

1
vote
4answers
36 views

$\mathcal{O}(n^n) > \mathcal{O}(n!) > \mathcal{O}(c^n) > \mathcal{O}(n^c) > \cdots $?

Is the following relationship correct $$\mathcal{O}(n^n) > \mathcal{O}(n!) > \mathcal{O}(c^n) > \mathcal{O}(n^c) > \mathcal{O}(n \cdot Log(n)) > \mathcal{O}( Log(n)) $$ Where ...
0
votes
1answer
16 views

How can i find the complexity of this recurrence relation?

Basically i'm having this recurrence relation which i don't know how to get the complexity of it by using the iterative method $T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if ...
0
votes
0answers
13 views

About the complexity of Mersenne numbers

In this page: http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test#Proof_of_the_Lucas-Lehmer_test In the end of this page I read this paragraph: The Lucas-Lehmer test, when used with the Fast ...
0
votes
1answer
36 views

Big o notation with division

I'm just starting to use big o notation and I just wanted to make sure I was on the right track. my algorithm is the following: (1/2)n^2+(1/2)n I came up with O(n^2) is that correct ?
1
vote
0answers
24 views

Oracles for TQBF

I've seen this question somewhere and I've been thinking about it a lot but couldnt think of an answer. Say you have oracles A and B for the TQFB (True Quantified Boolean Formula) decision problem, ...
0
votes
0answers
6 views

solving and predicting complexity of a statistical model

How difficult/time consuming would it be for a professional mathematician to model a temporal probability distribution of when an event will occur when the temporal history of that event occurring is ...
0
votes
1answer
24 views

Integer factorization complexity

Why isn't the problem of factoring an integer known to be in $P$? Isn't the naive algorithm of trying to divide a number by all the numbers up to its squre root polynomial?
0
votes
1answer
32 views

Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover?

As most of you know, the problem of finding a minimal vertex cover for an arbitrary graph is an NP-hard problem. I was wondering, if there existed a non-constructive way of calculating the size of a ...
1
vote
0answers
47 views

Combinatorial search by testing sets with fixed number of elements

I am struggling to see the complexity of the following combinatorial search problem. Could anyone help me? Consider a set $I$ of $n$ items known to contain $d$ defectives or less. Assume $d < ...
0
votes
1answer
38 views

Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
0
votes
0answers
11 views

Amortized analysis: Understanding the potential formula

The potential formula is: $$\overset{\wedge}{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$$ $\overset{\wedge}{c_i}$ the amortized time of operation $i$ is the actual time $c_i$ plus the change of the ...
0
votes
0answers
10 views

Asymptotics and function composition

In the following question: Big O and function composition It is explained that if $a, b, c, d$ are functions and $a = O(c), b = O(d)$ it doesn't mean that $a ∘ b = O(c∘d)$. However, what if we allow ...
1
vote
1answer
23 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
1
vote
1answer
23 views

Proving Priority Queue Operations Are Omega(log n)

From a textbook on computational problems, there's a question I've been pondering... Q: If a priority queue has operations to add a value and show/remove the smallest value, show that for an ...
1
vote
0answers
34 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
1
vote
1answer
50 views

Analyzing runtime of a nested for loop

// assume n is a power of 5 for (int i=1; i<n; i=i*5) for (j=i; j<n; j++) sum = i+j; I am supposed to find out how many times each line of code ...
3
votes
0answers
32 views

Philosophical implications of P vs NP proof?

Wikipedia article on P vs NP says that "a proof either way would have profound implications for ... Philosophy" without providing further details. So I was wondering what could be the philosophical ...
2
votes
3answers
31 views

Time spent to sort $10^7$ records with insertion sort

I am stuck with my revision for the upcoming test. The question asks" An implementation of insertion sort spent 1 second to sort a list of ${10^6}$ records. How many seconds it will spend to sort ...
0
votes
1answer
23 views

Proof of why the partition function Z in probabilistic graphical models (PGM) is NP-complete

I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard? I would like to see a full blown rigorous proof, however, I am as happy to get a ...
1
vote
0answers
25 views

Why is Chaitin's constant absolutely normal?

I have repeadetly seen claims that Chaitin's constant is normal in all bases (e.g. on Wikipedia), and I have also seen some proof sketches (e.g. here), but these only show the idea. For example, the ...
-1
votes
2answers
60 views

How do I show that $\sum_{i=0}^n i^2 = O(n^3)$?

Do I have to know the formula for the summation? Why?
0
votes
0answers
27 views

Simplify iterative logarithm

This is a homework question for my algorithms class and I have no clue how to start simplifying this function. I know log* is the iterative log function. It will equal the number of times you have to ...
0
votes
0answers
31 views

Are there problems known to be not in $P$ but not known to be outside $NP$?

Although most experts believe that $NP$ is not equal to $P$, for a long time I believed that of the two directions of attacking the $P$ vs $NP$ problem trying to prove that $P = NP$ is the more fun ...
0
votes
2answers
67 views

Is there a problem more difficult than NP-complete in graph theory?

There are some decision problems being NP-complete in graph theory, including the problem of deciding if a graph has a hamilton cycle, or determing the chromatic number. Since the number of labeled ...
0
votes
1answer
29 views

Prove that $\log^\alpha n = o( a^n )$

Please, how to prove: $\forall c \in \mathbb R_+$ $\exists n_0 \in \mathbb N_+$ $\forall n \ge n_0 :$ $log^\alpha n < c \cdot a^n$ for $ \\a>1$, $\alpha \in \mathbb R$ ? Thanks
0
votes
1answer
29 views

Sum of the series of numbers in an array

You are given a number $x$ and an array A[1,2....n] storing $n$ positive numbers such that $$A[1]+A[2]+....+A[i]≤A[i+1], \space \forall i<1.$$ Design a polynomial time algorithm to determine if ...
1
vote
1answer
28 views

How can I prove that $P \neq EXP$

It seems like $P\neq EXP$ is much easier than $P \neq NP$. How can I prove $P \neq EXP$? (Well, after all I want to know any proof technique of proving there does not exist any algorithm of certain ...
0
votes
1answer
60 views

Proof that $(1+\epsilon)^n = O(1+n\epsilon)$

How to prove that $(1+\epsilon)^n = O(1+n\epsilon)$ ? So far I proved the following: By the binomial, $(1+\epsilon)^n > 1+n\epsilon$ Also $\epsilon^n$ = 0 when n-> infinity. Edit: n constant. ...
1
vote
2answers
45 views

An algorithm which takes long time to halt

I want to find an algorithm such that takes 10 inputs as natural number returns 1 output as natural number between 1 and 10. (including 1 and 10) It means it should be a function f($x_0$, $x_1$, ...
1
vote
2answers
44 views

Difference between `log n` and `log^2 n`

I'm researching the different execution time of various sorting algorithms and I've come across two with similar times, but I'm not sure if they are the same. Is there a difference between ...
1
vote
1answer
58 views

Existence of graphs when given the degrees of all vertices

My question is: How to decide whether a graph is exist when given the degree sequence of all vertices? This question can be easily reduced to the {0,1}-solutions of integer linear equation ...
0
votes
1answer
34 views

Proving function complexity

I am trying to prove the following: Let $$f(n)=\sum_{i=2}^{n}\frac{1}{i \log i} $$ Where log denotes the natural logarithm. Show that: $$ f(n)=\Theta (\log \log n)$$ I am not sure how to go about ...
2
votes
0answers
16 views

Kleene normal form : elementary?

The Kleene normal form explains there are primitive recursive functions $T$ (a predicate indeed) and $U$ such that for any computable function $\phi_n$, and for any $x\in\mathbb N$ : ...
0
votes
0answers
13 views

Computational Complexity, graph colourable question

K-colourability is the problem of deciding, given a graph G=(V,E), whether there is a colouring X={1,2,...,k} of the vertices by k colours 1,2,...k, so that no two vertices that are joined by an edge ...
0
votes
2answers
24 views

How to show if a language is infinite, then there is no upper bound on the length of words in L?

L is a language over a finite alphabet. How to show that if L is infinite, then there is no upper bound on the length of the words within L? Can someone help me prove this.
4
votes
2answers
64 views

Optimal Box-in-a-Box-in-a-Boxing

As inspired by this closely related problem, suppose I have $n$ cuboid boxes, all with arbitrary (possibly random) finite dimensions. For any two boxes, $B_1$ with dimensions $w_1,h_1,d_1$, and $B_2$ ...
0
votes
1answer
23 views

Find $\sum_{i=0}^{\log n} \frac{1}{2^i}$

I'm not really sure how to solve summations, so any help would be great. In particular, I had thought that $n^2\sum_{i=0}^{\log n} \frac{1}{2^i}=O(n^2\log n)$ but it's actually $O(n^2)$, and I'm ...
2
votes
0answers
47 views

Is there a plausible outline of how geometric complexity theory could prove $P \neq NP$?

I've heard people saying that geometric complexity theory could be the key to showing $P \neq NP$, but when I've actually read about it it seems like it's concerned with other, perhaps analogous ...
6
votes
2answers
211 views

Why is there apparently a consensus on the P = NP question?

So through my years of education I have heard a lot about the famous $\mathrm{P}=\mathrm{NP}$ problem. I have seen that a significant number of mathematicians believe that this result is false (and ...
1
vote
1answer
57 views

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, ...
0
votes
0answers
34 views

How to prove that $f(n)=O(g(n))$ without using the definition of big oh?

I have to indicate for $f(n)=\log n$ and $g(n)=\sqrt[k]{n}$ if $f(n)=O(g(n))$ and if $g(n)=O(f(n))$. For $f(n)=O(g(n))$: I found it hard to prove it using the definition of big oh so I decided to ...
1
vote
1answer
15 views

Find functions which change asymptotic properties if raised to 2

Kindly give an example of positive functions f(n) and g(n) such that f(n) = O(g(n)) but it does not hold that 2^f(n) = O(2^g(n)). A friend asked this question as this came in one of his ...
2
votes
1answer
79 views

How to prove Big-Oh Equation e.g. $O({2}^{2n}) = O(2^n)$

I visit a course about complexity theory but I have some troubles to prove a Big-Oh equation like this: $O(2^{2n}) = O(2^n)$ $O(g(n))$ is a set of functions that fulfill following definition: The ...
1
vote
1answer
32 views

Complexity of finding $\alpha(G) + \omega(G)$

The CLIQUE NUMBER problem is NP Complete (due to correspondence with $3$-SAT); so is the INDEPENDENCE NUMBER problem (since $\omega(\overline{G}) = \alpha(G)$, or from CHROMATIC NUMBER problem). Can ...
1
vote
1answer
28 views

Strictly convex sequence

A sequence of numbers $A=(a_1, a_2, \dots, a_n)$ is called strictly convex, if there is a $k$, with $1 \leq k \leq n$ so that for all $1 \leq i \leq k-1$ we have $a_i>a_{i+1}$ and for all $k \leq i ...
0
votes
1answer
14 views

Asymptotic $T(n)=T(\sqrt{n})+1$

I would like to find the complexity of $T(n)=T(\sqrt{n})+1$ I did : $$T(n)=T(\sqrt{n})+1$$ $$T(n)=T(n^{1/2})+1$$ $$T(n)=(T(n^{1/4})+1)+1=T(n^{1/4})+2$$ And after $k$ steps : ...
0
votes
1answer
14 views

Dominant term- Complexity of function

I want to find the complexity of the function $g(n)=10 \cdot \log (n^{30}+30)+2$. We will find that $ g(n)=\Theta(\log n)$, right? But what can I say about the dominant term at the beginning?
1
vote
0answers
57 views

Datermine the time complexity of an algorithm calculating the sum of Euler $\phi$ function.

Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function. The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$. For simplify, I'd ...
1
vote
2answers
34 views

Which is the best way to find the complexity?

I want to find the asymptotic complexity of the function: $$g(n)=n^6-9n^5 \log^2 n-16-5n^3$$ That's what I have tried: $$n^6-9n^5 \log^2 n-16-5n^3 \geq n^6-9n^5 \sqrt{n}-16n^5 \sqrt{n}-5 n^5 ...
2
votes
0answers
59 views

Computing a “cheap” upper bound on the norm of the solution to a linear system

Consider the linear system $A x = b$, where $A$ is an invertible, $n \times n$, real matrix. I would like to compute a "cheap" upper bound on the (p-)norm of the solution; i.e. $\|x\|_p$. One can, of ...