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)

2
votes
4answers
130 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
0
votes
1answer
34 views

Computational complexity of Newtons Method

I'm trying to do a worst case complexity analsis of another algorithm that involves computing an nth root of a real number at each step. I have a bound B on the size of this number also n is fixed and ...
2
votes
2answers
71 views

Prove that $6^{\sqrt n} = O({n \choose n/2})$

Prove that $6^{\sqrt n} = O({n \choose n/2})$ I was able to show that prove that $6^{\sqrt n} = O({n \choose n/2})$ with defining $ n=2k$ and $ a_k= \frac {k!^26^\sqrt k} {2k!} $ and then show ...
1
vote
1answer
54 views

prove\disprove - there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$

there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$ Thought about $f(n) = |sin(n)|,\ g(n)= \frac1n$ then $f(n-g(n))= |sin(n-\frac1n)|$ and then for any ...
0
votes
1answer
53 views

Upper and Lower Bounds

The question that I'm having trouble with is: Prove that k/2 is a lower bound for √(n) I'm not sure how I would start this, can someone take a look at it and help me with it? I understand the ...
2
votes
0answers
71 views

Number of orderings of subset sums

In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...
0
votes
1answer
116 views

Solve linear programming given access to an oracle

This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant ...
1
vote
0answers
73 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
1
vote
4answers
114 views

What is an example for an algorithm which makes use the power of randomness?

Can someone give a (most simple) example for an algorithm on a machine, which has access to random numbers, and which is faster than any other known algorithm for the same task? My actual motivation ...
8
votes
2answers
623 views

Why are Polynomial Time Problems Considered Tractable, and Larger Times are Not?

I've been reading up on $P=NP$, problem tractability, etc. Here's my question: Why is it that we consider problems that can be solved in polynomial time - or algorithms/problem-solvers running in ...
0
votes
1answer
31 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
0
votes
0answers
472 views

Exact inversion of matrix complexity (by Gaussian elimination)

I would like to check if what I have done is correct. Please, any input is appreciated. Problem statement: Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination ...
2
votes
1answer
173 views

If P = NP, then 3-SAT can be solved in P

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists. $P = NP$ only says that we can decide whether a 3-SAT problem is ...
0
votes
1answer
39 views

Prove a language is NP-Complete

$A$ is NP-complete. $B$ is P. $A \cap B = \emptyset $ $A \cup B \neq \sum^{*}$ Prove that $A \cup B $ is NP-complete. How can I prove this ? I think if anything can be P-reducible to A then it ...
4
votes
3answers
97 views

$NP$ problems not known to be in $P$ and not known to be $NP$-complete

I've read that solving Pell's equation is neither known to be in $P$ nor known to be $NP$-complete. What are other natural and important examples of such problems?
0
votes
1answer
18 views

Stability and complexity of some functions

Can someone check if my solutions/arguments on this exercise are correct? Thanks! Are the following statements true or false? $\sin (x)=\mathcal{O}(1)$ as $x \rightarrow \infty$ $\sin ...
2
votes
3answers
376 views

Project Euler's Problem Number 88

I am tackling Project Euler's problem number 88, which in a nutshell reads: Let $S_n$ be the set of sequences of natural numbers $(s_1,s_2,...,s_n)$ where $s_1\leqslant s_2\leqslant\cdots\leqslant ...
1
vote
2answers
168 views

Why is the decision problem of the “Travelling Salesman” $\in \mathcal{NP}$?

One of the most well-known problems that belongs into the class of $\mathcal{NP}$-complete problems is the Travelling Salesman Problem. However, I fail to see why it is "so obviously" in ...
2
votes
0answers
62 views

Asymptotic behavior of $L^2$ norm for increased matrix dimensions

I am playing with matrices which are linear combinations of identity matrix, Pauli spin matrices, $\sigma_x$ and $\sigma_z$ or their tensor products. For example, let the matrix be $H$. So, $H$ could ...
0
votes
1answer
322 views

Big Oh Notation for a Recursive Algorithm

I have a question that I'm unsure of: Express the complexity of the following method using big-O notation. You must explain how you arrived at your answer. What value is returned by the call ...
0
votes
1answer
101 views

Expected running time

Suppose A = A[1] . . .A[n] of length n (where A[i] is either 0 or 1). We want to determine if at least half the elements in A are 1’s. ...
0
votes
2answers
45 views

What does $\text{poly}$ stand for in $O(\log^{10.5}n \cdot \text{poly}(\log \log n))$?

I posted this question on cstheory and found that "poly(f(n))" is shorthand for "polynomial in f(n)" or $f(n)^{O(1)}$, hence poly(log log n) is shorthand for $(log log n)^{O(1)}$. However, I don't ...
1
vote
1answer
57 views

Course-by-values recursion

I have many questions in my textbook of the kind: Assume $g$ is primitive recursive and assume $f(0)=c_0,\dots,f(n-1)=c_{n-1}$ $f(x+n)=g(<f(x),\dots,f(x+n-1)>)$ Prove that $f$ is primitive ...
0
votes
1answer
154 views

“Nested” recursion preserves primitive recursive functions

Problem: Assume the functions $f$, $\pi$, and $g$ are given. They take one, two, and three arguments respectively. Prove a unique function $h$ exists such that: $$h(0,y)\cong f(y)$$ $$h(x+1,y)\cong ...
0
votes
2answers
52 views

Not able to solve the below mentioned inequality. Someone please explain me it's solution.

This is an in equality with a solution given below. I'm not able to understand it. It will be very helpful if someone can help me understand it. Thanks. The inequality is in the image attached with ...
1
vote
1answer
233 views

Converting 2 sat formula into an implication graph.

Both wikipedia and my lecturer explained how the 2 satisfiability problem work. However, I am finding it really hard understanding how this formula: ...
0
votes
1answer
47 views

Turing machines and tape complexity

Are the following statements true and/or false? There is a total function $g: \mathbb{N} \rightarrow \mathbb{N}$ so that for each Turing machine $M$ and each natural number $t$ we have: (*) ...
4
votes
3answers
208 views

$\log(n)$ is what power of $n$?

Sorry about asking such an elementary question, but I have been wondering about this exact definition for a while. What power of $n$ is $\log(n)$. I know that it is $n^\epsilon$ for a very small ...
8
votes
1answer
124 views

Finding the smallest set on which a group acts faithfully

Given a finite group $G$, how efficient can one make an algorithm to find the size of the smallest set $S$ such that $G$ is isomorphic to a group of permutations of the members of $S$? And does the ...
2
votes
1answer
55 views

Proving $\sum_{k=1}^n \sqrt{k}=\Theta(n\sqrt{n}).$

How can I prove this complexity? $$\sum_{k=1}^n \sqrt{k}=\Theta(n\sqrt{n})$$ The theta notation means a quantity bounded in the limit both above and below by constant multiples of the given ...
3
votes
3answers
177 views

lower bounds on the running time

There are some problems with non-trivial lower bounds for working time of algorithm (that solve this problem): sorting, copying words on Turing machine... What are some modern methods for proving ...
1
vote
0answers
47 views

If P = NP can asymmetric key exchanges still exist?

One functions are easy to compute (ie polynomial time checking) but hard to reverse. if P = NP does that mean that asymmetric key exchanges will be reduced from polynomial computation time and ...
0
votes
1answer
64 views

I need a layman's blurb on 'time' (as in for example, polynomial time)

I took a rather winding and incomplete road through maths (and comp-sci) in college, so some things I get, and some things I must have missed. I need to wrap my head around what Math and Computer ...
0
votes
1answer
69 views

Prove $an\log(n)+3n = \Theta(n\log(n))$

Using the asymptotic definition of $\Theta(.)$ I need to show that: $$an\log(n)+3n = \Theta(n\log(n))$$ for some $a$, fixed constant. My attempt In order to prove what's above, I need to find a ...
1
vote
0answers
103 views

Derive 3D point array from multiple 2D projections of same point array

Let's assume that we have an array of $n$ 3D points, we don't know their coordinates (thus we have $3n$ indeterminate scalar values). We also have $m$ 2D projections with known coordinates (thus we ...
0
votes
0answers
74 views

Definition of a Turing Machine

Could someone explain the following definition of a Turing Machine? A Turing Machine $M$ is defined formally by a tuple $(\Sigma, Q, \delta)$ Where $\Sigma$ is a finite set representing the number ...
0
votes
1answer
39 views

Need help figuring out function complexities the right way

I solved the following problem by plotting a graph and comparing the complexities. The picture below show the question along with my answer and the TA's corrections. Can someone please tell me what ...
1
vote
2answers
82 views

Are the primes compressible?

Take a list of the first $n$ primes $P_n=\{2,3,5,7,11,\ldots\}$ and convert the sequence into a binary string $$S_n = 101110111\ldots$$ Compress the string with your favorite compression algorithm ...
3
votes
2answers
70 views

Question about polynomial $\sum_{j=1}^n j^k$

How could I prove that $ 1^k + 2^k + \cdots + n^k \in \Theta(n^{k+1}) $ or, equivalently, $$ 0 < \lim_{n\to\infty}\frac{\sum_{i=1}^n i^k}{n^{k+1}} < \infty? $$ I would appreciate a hint rather ...
2
votes
1answer
36 views

Complexity class of generating all permutations

What is the complexity of the following problem (i.e. to what complexity class does it belong)? Given a positive integer $n$, provide all permutations of the sequence $\{1, 2, \ldots, n\}$.
0
votes
1answer
215 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
1
vote
1answer
68 views

What is the difference between $O(N/ \log_2(N))$ and $N-o(N)$?

On the second page of this paper under the introduction section they say "We first show that for the set of parameters considered by [16], the function family has $O(N/ \log_2(N))$ simultaneously ...
0
votes
1answer
34 views

Proof of Complexity

If I want to prove that $f=O(g)$ for $f(x)=x^{1/2}$ and $g(x)=x^{2/3}$, is it sufficient to say that $\lim_{x \to \infty}f(x)/g(x)=0$? I'm not sure if this is a convincing enough argument or more ...
3
votes
0answers
49 views

How quickly can one compare exp(m/n) to a given rational?

For positive integers $\hspace{.06 in}m_{\hspace{.02 in}0}\hspace{.02 in},n_0\hspace{.02 in},m_1,n_1\:$, $\;$ how difficult is it to decide whether $$\exp\left(\hspace{-0.03 in}\frac{m_{\hspace{.02 ...
1
vote
0answers
50 views

Definition of Complexity Classes

The definitions I've seen for 'complexity class' all seem to be variations on "the set of problems that can be solved by an abstract machine of type $M$ using $O(f(n))$ of resource $R$, where $n$ is ...
2
votes
2answers
93 views

Let $C$ be a set of sets defined as follows,

I'm in Theory of Computation, I've already taken Set Theory so I'm familiar with the terminology but this question is not making sense to me. Let $C$ be a set of sets defined as follows: ...
2
votes
1answer
35 views

“Kolmogorov complexity with time”

Kolmogorov complexity of object is minimal length of program that print this object. 1)Kolmogorov complexity is not a computable function. 2)If there is little program that print object for billion ...
1
vote
0answers
52 views

Why is positional number system natural?

In the theory of computation, one mainly deals with maps $\Sigma^*\rightarrow\Sigma^*$. To discuss computation on other sets $X$ than $\Sigma^*$, one fixes a representation ...
2
votes
0answers
428 views

Solving large, sparse system of linear equations

I have a system of linear equations as follows: $$(A+I)x=B$$ where $I$ is the $n\times n$ identity matrix, $A$ is a $n\times n$ matrix such that the first and last rows are blank, and, for every ...
0
votes
2answers
82 views

For $f(n) = \log n$ and $g(n) = n^c$, where $0 < c < 1$, is it always true that $f$ is $O(g)$?

In complexity analysis, basic functions you encounter are functions like $f_1(n) = \log n$, $f_2(n) = n^2$ and $f_3(n) = n^3$. It is fairly obvious to me that $f_1$ is $O(f_2)$ and $O(f_3)$, but it is ...