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)

4
votes
3answers
493 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 $\...
10
votes
1answer
160 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
57 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
245 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
59 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
91 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
91 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
151 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
139 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
54 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
109 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
73 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
39 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
453 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
72 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
36 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 ...
4
votes
0answers
56 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 in}...
1
vote
0answers
61 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
123 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: $\emptyset\...
1
vote
1answer
461 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
2
votes
1answer
43 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 ...
2
votes
0answers
61 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 $\gamma:\Sigma^*\...
2
votes
0answers
717 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
88 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 ...
2
votes
1answer
66 views

Calculating modular inverses with limited multiplication

Question Given $\alpha_1,\dots,\alpha_k \in \mathbb{Z}_n^\ast$, I want to compute $\alpha_1^{-1},\dots,\alpha_k^{-1}$ by computing only one multiplicative inverse and less than $3k$ multiplications ...
0
votes
0answers
117 views

Verifying Algebraic Formulas

Say you are given an arbitrary Algebraic Formula: $$G(u_1,u_2,u_3...u_n) = 0$$ Where the expression $G$ is allowed to utilize: $+, - , *, /$ however desired $()$ however desired The operator $P(...
3
votes
1answer
363 views

Bound on total divisions of Euclid's Algorithm.

Question Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ ...
2
votes
1answer
122 views

Will a problem be polynomial time solvable if a mathematician gives a procedure?

For a decision problem, if a mathematician finds a simple polynomial time procedure that solves it, does it mean that the problem is polynomial time solvable? For example, consider a decision problem:...
2
votes
0answers
49 views

Abelian SubGroup Variant:

Consider the following problem: Find integers $x_1, x_2, x_3,\dots, x_n$ Such that: $$P(x_1,x_2,\dots, x_n) = Q$$ for some integer $Q$ and polynomial $P$ where for all permutations of any set of ...
4
votes
1answer
5k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree [duplicate]

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
2
votes
1answer
47 views

Differentiating between prime/semi-prime and other integers

Does there exist a test that checks if a number is prime or a semi prime in polynomial time? I am aware that AKS can be used to check primality but what about semi primality? ========================...
1
vote
0answers
76 views

Quadratic Diophantine Primality Testing

Define a 2-Quadratic Group Operation as the following: A 2nd degree polynomial of the form: $$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 $$ Define a primal 2-quadratic group number as an ...
3
votes
5answers
750 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
2
votes
2answers
126 views

Computation of the mean of a random variable to estimate algorithm complexity

I made an incremental algorithm which I would like to evaluate the complexity. The algorithm works with a sliding window of size n. To study the complexity, the window is considered full and the data ...
2
votes
1answer
152 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
2
votes
2answers
232 views

Find the smallest natural number not in a given set of integers

What is the computational complexity of this task? The goal is to compute the number $x=\min(\Bbb N\setminus A)$, where $A$ is the input list and the complexity parameter is $n=|A|$ (which is finite). ...
1
vote
0answers
84 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
9
votes
5answers
575 views

A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
3
votes
1answer
134 views

Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
2
votes
1answer
26 views

Complexity of finding fixedpoint

Suppose I have a fixed $n$-dimensional vector space $V$ over a field $F$ and I have a sequence of $n'$-linear transformations $G_i:V\rightarrow V$, $i \leq n'$. Further suppose I know that there is a (...
0
votes
2answers
169 views

Is polynomial time reduction commutative?

True or False: $D_1$ and $D_2$ are decision problems, and $D_1 \leq_p D_2$, then cannot be that $D_2 \leq_p D_1$ I think it is false because we already have a mapping for all yes instance from $D_1$ ...
2
votes
0answers
131 views

Solving a particular system of Diophantine equations in $n$ variables (Frobenius equations)

I have a particular system of linear Diophantine equations in $n$ variables for which I need to find all nonnegative integer solutions. Specifically, they are Frobenius equations, meaning the ...
0
votes
1answer
90 views

Cyclic Groups: Modulo operations in exponents possible?

I'm trying to follow CCat's Zero Knowledge Proof example, which was quite similar to the $\Sigma$-protocol example in my books. And whith both of them I'm struggeling. When I try to test CCats Example:...
2
votes
2answers
573 views

Solving Summation Expressions

I would like to know how do you solve summation expressions in an easy way (from my understanding). I am computer science student analyzing for loops and finding it's time complexity. e.g Code: <...
1
vote
0answers
75 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
0
votes
1answer
390 views

Solving a recurrence relation with floors and comparing it with other complexity classes

The problem that I am struggling with is the recurrance relation $T(n) = \lfloor(T(n/2))\rfloor + \lfloor(log \space n)\rfloor$ Where $T(1) = 1$ I am supposed to answer true/false to each of the ...
3
votes
1answer
265 views

Using the definition of big-oh notation, show that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.

This question had been on my midterm in a course I took last year: Prove that for any $k,\gamma>1$, $n^k=O(\gamma^n)$. Intuitively, this makes sense. Even the fastest exponential algorithm (...
1
vote
0answers
42 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
4
votes
4answers
563 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
7
votes
1answer
150 views

complexity of matrix multiplication

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate $\operatorname{...