Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

-1
votes
1answer
15 views

Verification of $F(m)^{d} \pmod n \equiv m$ with very large inputs, where $F(m)=m^e$

Does anyone have the computational power to check whether or not $F(m)^{d} \pmod n \equiv m$, where the values of the variables are found below. According to Wolfram Alpha, I found the result of the ...
1
vote
2answers
14 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
29 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
19 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
29 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 ...
-2
votes
0answers
15 views

Please define in details, running time complexity of algorithm [on hold]

yz=0; xw=0; for(i=m; i>-6; i=i-6) {XW++;} for (i=n; i>-2015; i=i*5) {yz=yz+1}
0
votes
1answer
8 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? ...
1
vote
1answer
20 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
18 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
0answers
25 views
+50

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
23 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 ...
0
votes
0answers
19 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
22 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
19 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
17 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
36 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 ...
0
votes
0answers
11 views

Turing machine that modifies each cell that contains a certain input one time at most

If I have a single tape turing machine running on some input $x$, where it modifies each part of the tape with $x$ one time at most...would the TM be decidable? Any advice or guidance appreciated; ...
1
vote
4answers
33 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
12 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
28 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
17 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
29 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
46 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
35 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
10 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
21 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
22 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
49 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
30 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
30 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
20 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
30 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
64 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
27 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
44 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
39 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
53 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
33 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$ : ...