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
2answers
30 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ ...
0
votes
1answer
54 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
1answer
29 views

Algorithm to find string

Given a string $w$, we want to find the last string in the list, that precedes alphabetically $w$ and ends with the same letter as $w$. Example: $\text{ w=crabapple }$ $L=\langle \text{canary, cat, ...
1
vote
0answers
48 views

an instance of NP-complete

The cafeteria serves $m$ different kinds of food, $F = \{ f_i \}_{i = 1}^{m}$. The fruit are grouped into $n$ different types of bags $B_1, \cdots, B_n \subseteq F$. (The same kind of fruit might be ...
0
votes
1answer
22 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
2
votes
1answer
68 views

Reduction of 3-SAT to 3-COLOR

The decision version of the 3-COLOR problem is the problem of deciding whether an input graph G(V, E) can be colored using only 3 colors so that no 2 adjacent vertices have the same color. I had ...
0
votes
1answer
19 views

Properties of carry in base $b$ multiplication

Consider $n$ bit numbers $A$ and $B$. Let they be represented in base $b$. When you multiply $A$ and $B$ using school multiplication: $(1)$ how many carry propagations can one expect? $(2)$ what ...
1
vote
1answer
65 views

Understanding the complexity class $P^O$ for randomized oracles

We know from Toda's theorem that $PH \subseteq P^{PP}$. What do we know about the following classes? $$ P^{ZPP}, P^{RP}, \text{ and } P^{BPP} $$
0
votes
2answers
27 views

Show recurrence $T(n)=2*T(n-2)+3$ satisfy $T(n)=O(2^{n/10})$

Well the original question was asking about Tower of Hanoi. First I need to come up with a recurrence for the Tower of Hanoi with 4 poles. (Please note the original tower only consist of 3 poles) The ...
1
vote
1answer
28 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
1
vote
0answers
37 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
1
vote
1answer
45 views

Prove that the subset sum problem with fixed size and number reusability is NP complete

I'm trying to solve the following problem: There are B (B is allowed to vary) lists of unspecified size containing integers. Pick a number from each list so that the sum of all the picks is exactly ...
0
votes
1answer
19 views

Complexity of Subset-Sum when the target sum is a constant

The Subset-Sum decision problem is: Given a set of n non-negative integers S, is there a subset of S that sum to k? If S and k are inputs, the problem is known to be NP-Complete. What about ...
2
votes
1answer
39 views

Efficient computation of a product of $3$ matrices.

Let $U\in\Bbb{R}^{d\times n}$, such that $U^\top U=I_n$, where $I_k$ denotes the identity matrix of order $k$. Also, let $A\in\Bbb{R}^{n\times n}$ be an $n\times n$ real symmetric matrix. The ...
1
vote
4answers
44 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
20 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
18 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
122 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
29 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
10 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
36 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
81 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
50 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
47 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
15 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
19 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
50 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
36 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
35 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
69 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
55 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
33 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
51 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
46 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
37 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
80 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
35 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
52 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
113 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
72 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
37 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
36 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
30 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.
5
votes
2answers
90 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
28 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
53 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 ...