Tagged Questions

Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
0answers
10 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
41 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.
1
vote
2answers
33 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
35 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
49 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
30 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
9 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
23 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
56 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
44 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
190 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
48 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
33 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
72 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
27 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
21 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
12 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
13 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
49 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
33 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
51 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
30 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
0answers
26 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
412 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
24 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
51 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 ...
0
votes
0answers
16 views

Big Oh proof. Need help finding c constant

Ok I have the equation . I have compared each term with 2^n and proved that 2^n is greater for some n_0. My problem is how do I gather the terms up and find the c? $ \sqrt[]{2}^{\log n} + \log^2 n + ...
3
votes
0answers
111 views

indices set and halting problem in computation course

I ran into a multiple choice question that confused me with this notation. anyone could help me? this is adapted from an old class quiz in Calgary. Suppose A is be indices (i think index set) of type ...
6
votes
0answers
80 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
35 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
24 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
32 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
30 views

Help with understand the growth order of functions

I am taking an Algorithms class and I understand everything that relates to the asymptotic growth and Order of growth for a given function (Theta, Omega, etc). However, I am having trouble in ...
0
votes
0answers
13 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
29 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
24 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
272 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 ...
0
votes
0answers
32 views

Prove or Disprove Asymptotic Complexity

Not sure how to prove or disprove this. $$\min\{f(n), g(n)\} \in \Theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right)$$ Could someone please give me a hint on how to approach this?
1
vote
1answer
26 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
35 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
32 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
32 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
40 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
34 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
17 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 ...
0
votes
1answer
56 views

What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
0
votes
0answers
32 views

Find two element $x_k$ and $x_l$

Let $S=\{ x_1, x_2, \dots, x_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $x_k$ and $x_l$ of $S$, ...