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)

0
votes
1answer
37 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 ...
2
votes
1answer
45 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
62 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
35 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
76 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
31 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
34 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
32 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
63 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
50 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
90 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
68 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
35 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
29 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
2answers
29 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
84 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
27 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
51 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
222 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
65 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
39 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
18 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
101 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
47 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
55 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
21 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
37 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?
2
votes
0answers
74 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
37 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
80 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 ...
1
vote
2answers
43 views

How do I find the big oh of $\sqrt[k]{n}$?

I have a problem where $f(n)=\log n$ and $g(n)=\sqrt[k]{n}$ and I have to prove that $f(n)=O(g(n))$. I'm using the big oh formula: $$ \begin{align} f(n)&\leq cg(n)\\ \log n&\leq c ?? ...
0
votes
1answer
31 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
6
votes
3answers
422 views

Is O(n) a proper class or a set?

Is $O(n)$ as the collection of all functions that are bounded above by $n$ a proper class or just a set? What about $O(\infty)$?
0
votes
2answers
43 views

Clarification on the big oh of the sum of two functions

In computing the asymptotic complexity of the sum of two functions, one theorem states that if $\large\lim_{n\rightarrow\infty}\frac{f_2(n)}{f_1(n)}$ exists, then the asymptotic complexity is ...
1
vote
0answers
73 views

Big-O estimate (smallest order)

I'm trying to give a big-O estimate for each of these functions, where I want to use a simple function $g$ of smallest order. I have them all done I just wanted to someone to run through and check ...
2
votes
0answers
85 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
3
votes
2answers
55 views

Is drawing the Voronoi diagram NP-hard?

Suppose we have a set of points in the plane. Is computational complexity defined to draw the Voronoi diagrams of these points? Since the plan is continuous I don't see how complexity can be defined. ...
0
votes
2answers
64 views

Word Form of Big O Notation

O of (the contents of the parentheses) Is this the correct way to say an expression with big O notation in words, just as y=f(x) is read y equals f of x? The expression with the big O followed by ...
1
vote
2answers
50 views

Is there a relationship between the clique of a graph and colouring of a graph?

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the ...
0
votes
0answers
69 views

Gauss Jordan vs Gaussian Elimination and Back Substitution Efficiency

I have an assignment that claims that Gauss-Jordan Elimination has the same efficiency Gaussian Elimination with back substitution. I get this part; but the assignment asks me to show that from a ...
1
vote
1answer
38 views

Multiply two polynomial in O(nlog n) time

In order to multiply two polynomial , we need O(n^2) complexity. Is it possible to perform the multiplication in O(nlog n) time??
0
votes
0answers
30 views

Hardest case in checking for hamiltonicity?

The problem of checking if a given graph has a hamilton-cycle, is NP-complete. However, in practice, the known algorithm work well. I wonder if sparse graphs (only a few edges) are more difficult ...
10
votes
2answers
290 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
1
vote
1answer
34 views

Recurrence Algorithms

What is the best method of solving non standard recurrence algorithms? In particular something like the following: What would be it's tight bound in Theta notation? $$ n \in N\\ T(n) = \sqrt{n} \; ...
1
vote
0answers
42 views

Constructing a “one-way function” of two variables (a.k.a “stop my friend from hacking my game”)

This might be more of a computer science question than a mathematics one; I thought I'd start here but perhaps people might want to point me to a better forum, if this isn't the right one. ...
0
votes
1answer
39 views

Proving $\lg n!=\Omega(n\lg n)$

In the answer given in the book for the proof of $\lg n=\Omega(n\lg n)$ there are several steps which I don't understand . $$\lg n!=\lg n+\lg(n-1)+\lg(n-2)+ ....+\lg(2)+\lg 1$$ Then it says that ...
0
votes
1answer
36 views

Does this loop run in $\mathcal{O}(n^4)$ time?

A double loop is given: int sum = 0; for (int i = 0; i < N*N; i++) for (int j = i; j < N; j++) sum++; My analysis: The inner loop runs $n$ ...
0
votes
2answers
45 views

Is my method of computing the running time correct?

Okay, so this is the code for which I need to compute the running time: ...
2
votes
1answer
38 views

Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
0
votes
1answer
34 views

How to derive time complexity of following method.

I have one algorithm for which I have to find time complexity of number of time x=x+1 is executed: j=n; while(j>=1){ for i=1 to j x =x+1 j=j/2 } What ...