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)

0
votes
0answers
15 views

How to show that if a relativized PH collapses, then PH collapses itself

Due to a lack of activity on the CS.SE, I'm asking this question here. Let $A$ be an arbitrary set in PH. Suppose PH$^A$ collapses. I am now asked to show that PH itself must collapse. I have ...
0
votes
0answers
32 views

The complexity of bubble sort and insertion sort for a list with a given number of inversions

Let the length of a list be $n$, and the number of inversions be $d$. Why does insertion sort run in $O(n+d)$ time and why does bubble sort not? When I consider this problem I am thinking of the ...
0
votes
0answers
71 views

Calculating the average case complexity for finding the maximum number in an array

Algorithm: Given a non empty array with $N$ Numerical values, the algorithm finds the location LOC and the maximum value MAX of the largest element of DATA. Initialize K:= 1, LOC:=1, MAX:=...
3
votes
3answers
95 views

Why isn't integer factorization in complexity P, when you can factorize n in O(√n) steps?

It is said that integer factorization is an NP problem. Why isn't it P? You can solve it in $O(\sqrt{n})$ time with trial factorization, and since $\sqrt{n} = n^{1/2}$, to me that looks like a number ...
0
votes
1answer
49 views

Factorial grow faster than Exponential - permutation case

It is said that factorial grows faster than exponential, but in the case of permutation: ...
0
votes
0answers
35 views

Converting a for loop to a sum

I'm trying to convert the following for loops to sums, but I'm getting a little confused about the upper limits: for(i=2; i <= n; i*=i) ...
0
votes
0answers
35 views

Complexity analysis of finding the roots of a polynomial

Hypothesis: all the set elements and polynomials (coefficients) are defined over a field $\mathbb{F}_p$ where $p$ is a large prime number. .................................................... ...
0
votes
1answer
16 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
0
votes
1answer
17 views

How do you express “additional complexity”?

Let's say I have two algorithms, one of which is less efficient in the sense that the complexity in the $\mathcal{O}$ notation has an additional factor $n$ (so for example, one is $\mathcal{O}(n^2)$ ...
1
vote
1answer
39 views

Runtime-complexity of a pseudo code.

Give an analysis of the running time of the following code snippet. ...
1
vote
1answer
35 views

Show that a Function is Big Theta Using Limits

I'm asked to show that: $f(n) =n^2+ 3n $ is $ \theta$$(n^2)$ using limits. I know that without limits I can usually solve for a constant, and easily show that this is true, but I'm not too familiar ...
2
votes
4answers
38 views

O(n) of given code

sum = 0 for (i = 0; i < n; i++) for (j = 0; j < i * i; j++) for(k = 0; k < n; k++) ++sum Here is my work The outer most loop: $$...
1
vote
1answer
44 views

Meaning of “polynomially larger”

For example Is $n$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? Is $n^2$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? I am trying to understand the difference ...
0
votes
0answers
49 views

Simplify sum with binomials

An algorithm finds prefixes of given length k from given word with length n. It is required to find the time complexity of given algorithm. It is easy when no nodes get cut off in its recursion tree (...
-1
votes
1answer
37 views

Conditions for embedding between non-oriented graphs [closed]

I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ ...
0
votes
1answer
40 views

How to find the Big-O of the difference/quotient of two funtions

I'm not sure if what I'm asking even makes sense but it's a property of big-O that if $T_1(n) = O(f(n))$ and $T_2(n) = O(g(n))$, then $T_1(n) + T_2(n) = O(f(n) + g(n))$, or less formally its $O(max(f(...
1
vote
0answers
28 views

What is the Computational Complexity of Minimising a Linear Function over a General Convex Set?

Is the computational complexity of finding or approximating $\inf\{c^Tx:x\in X\}$ (where $X$ is a compact convex given explicitly or by some reasonable oracle) known? EDIT: Suppose we had an ...
0
votes
0answers
129 views

Counterexample for Algorithm of Isomorphism testing of Non-Symmetric Matrices

Claim: $E, F$ are non-symmetric 0-1 matrices of dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check ...
0
votes
2answers
27 views

Design a finite automata by checking division of number of characters

I need to design and draw a finite automata that can accept the letters {a,b}. The number of the the letters a should be devided by 3, and the number of the letter b should be devided by 2. For ...
0
votes
1answer
22 views

complexity of building heap: why can one substitute a bounded infinite series into a bounded sum?

Partially into the derivation, the author substitutes the result of this infinite series, $$ \sum_{h=0}^\infty hx^h = \frac{x}{(1-x)^2} $$ into the bounded sum, $$\sum_{j=0}^h j\left(\frac{1}2\...
0
votes
1answer
30 views

Big-O complexity of calculation: Drawing a non-colliding subset of k elements from n total

I'm trying to understand the computational complexity of this pseudocode: ...
0
votes
0answers
28 views

Arithmetic complexity of mod powers

Given $a,b,p\in\Bbb N$ what is the computational complexity of computing $a^{p^b}\bmod p$? Is it $O((\log a)(\log b)(\log p))$ arithmetic operations on $\log p$ sized words? $p$ need not be prime.
1
vote
0answers
29 views

“Relative unsatisfiability” of SAT instances

There's a natural way to view any SAT instance as a variety: just replace the Boolean algebra $2$ of truth values with the corresponding Boolean ring $\mathbb{Z}/2\mathbb{Z}$. (See my answer to Is ...
5
votes
2answers
177 views

Is there an equivalent concept of a “variety” for SAT?

Couldn't find anything via google - I was wondering what work is out there looking at SAT problems from the perspective akin to an algebraic variety, e.g. a set of variables $X_1=$true, $X_2=$false, .....
1
vote
1answer
46 views

Why can't this be done with Master Theorem

Apparently recurrences like this cannot be solved with the Master Theorem: $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$ Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) ...
0
votes
1answer
14 views

Estimate logarithmic complexity

I have data (running time $T$ and problem size $N$). If I suspect that there is a polynomial relationship in the form $T=a N^b$, I can plot a log-log graph and work out the gradient, as stated on the ...
-4
votes
1answer
34 views

Compute bits per second [closed]

We know a computer can code 1024 bits/sec using a RSA modulus of 1536 bits and the running time of modular exponential with modulus $n$ is $O(\ln^3(n))$. Using a key of 2048 bits, how many bits per ...
3
votes
1answer
68 views

Problems in NP but not in NPc

Are there currently any known problems that are in NP but are known not to be NP complete?
1
vote
0answers
61 views

A polytime language with no subsets of lesser time complexity

For any integer $l>0$ does there always exist a language with time complexity of order $O(n^l)$ such that it has no subsets of a lesser time complexity ie $O(n^m)$ for any $m< l$. We talk of ...
4
votes
1answer
295 views

Algorithm. Minimum area of a square enclosing given set of points .

I am learning about the science of algorithms and I'm studying some problems with their optimum algorithm. The problem I describe below is one of them. I need a lower and an upper bound of its ...
1
vote
2answers
49 views

$2^{O(\log \log n)} = O(\log n)$ prove or disprove

I need to prove or disprove this: $$2^{O(\log\log n)} = O(\log n)$$ I haven't found anything like that through search. I would like to have some help. Thanks.
1
vote
2answers
44 views

How can I solve this logic statement with explanation?

There is a pack of cards and every card has a number on one side and a letter on the other. The statement that every card in this pack that has an A on one side has a 3 on the other side is true. The ...
1
vote
0answers
15 views

How to adjust finite differencing method for mapping from $\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ where $n = m^{2}$?

So I'm supposing $F:\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ is differentiable, and I have MatLab code that evaluates $F$ at an arbitrary $x$ in $q$ flops. I know that given $F(\bar{x})$ where $\...
1
vote
2answers
41 views

Computable problem

A mathematical problem is computable if there is an algorithm that decides/solves this problem, right? Can you give an example of such a problem?
6
votes
0answers
58 views

Find a region with maximum sum of top-K points

My problem is: we have $N$ points in a 2D space, each point has a positive weight. Given a query consisting of two real numbers $a,b$ and one integer $k$, find the position of a rectangle of size $a \...
8
votes
4answers
172 views

Computing the first $n$ values of the Liouville function in linear time

Is it possible to compute the first $n$ values of the Liouville function in linear time? Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out ...
4
votes
4answers
74 views

Origin of the phrase 'in polynomial time'

What is the origin and context of the phrase 'solvable in polynomial time' in computer science? Are they related to the notion of 'polynomials' in mathematics?
4
votes
1answer
41 views

Expected value of best possible earnings in a fair betting game.

You are playing a fair betting game. i.e. Every round you win 1 dollar with probability 0.5 or lose 1 dollar with probability 0.5. You play a total of $T$ rounds in a game. Suppose in hindsight, you ...
0
votes
3answers
59 views

How to compute for the time complexity of this triple nested loop

for (i=1 to n-1) { for (j=i+1 to n) { for (k=1 to j) { } } } The Answer is: $$\frac{n^3}{3} - \frac{n}{3}$$ I'm trying to use summation to solve for ...
3
votes
2answers
66 views

Expressing 3SAT clause as a 2SAT formula

I am wondering about expressing $3SAT$ clause (disjunction of 3 literals) as a $2SAT$ formula. If it would be possible then $P=NP$ Let's consider a clause of the form: $x_1 \vee x_2 \vee x_3$ The ...
0
votes
0answers
25 views

What exactly is the definition of an evaluation oracle?

What is the definition of an evaluation oracle in complexity theory?
-1
votes
1answer
73 views

Lower bound for two eggs problem

I have just read about two eggs problem. I know that with decreasing amount of jumps we can reach worst case scenario of first jump $a = \sqrt{2n}$, $n$ is the number of floors, how about the lower ...
1
vote
3answers
140 views

Calculating Running Time (in seconds) of algorithms of a given complexity

I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time. I was wondering how to find the ...
2
votes
0answers
51 views

Is it possible to reduce Theory of Rationals to Theory of Natural Numbers?

Is the following possible ? $$ Th( \mathbb{Q}, +, \leq ) \leq^{\log}_m Th( \mathbb{N}, +, \leq )$$ I believe it is not possible since Natural Numbers are not dense. It is also not possible $$ Th( \...
1
vote
0answers
28 views

tight bound for a finite sum involving harmonic series

I want to a know tight bound of this quantity when $n$ is even $$\sum_{k=1}^{n/2}\sum_{m=n-k}^{n}\frac{1}{k(k+1)m}$$. I simplified the expression and it comes like $$H_n[1-\frac{1}{n/2+1}]-\sum_{k=1}...
0
votes
0answers
39 views

How could I modify a Turing machine that attempts to move the head past the leftmost square(crash) on some inputs so that it doesn't crash at all?

Suppose that M is a TM that crashes on some inputs. How would I modify M so that the new machine accepts the same language but does not crash on any input ?
0
votes
0answers
8 views

What is the time complexity of parallel approach of stable marriage?

There are many approaches to implement the stable marriage algorithm in parallel, I'm referring to the approach where the algorithm is divided into two phases. In the first phase the all the men are ...
0
votes
0answers
28 views

Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because cnf makes it ...
7
votes
4answers
258 views

How many possible phone words exist for a phone number of length N when also counting words less than length N within that phone number?

The phone words problem find all possible words that can be derived from a phone keypad, "words" do not have to be English dictionary words, for this question, words can be any combination of letters ...
1
vote
1answer
38 views

Algorithmic efficiency of rotating a point

I am trying to calculate the algorithmic effciency (Big-O) of rotating n 3-D vertices using the rotation matrix: $\begin{bmatrix}1 & 0 & 0 \\0 & cos(a) & -sin(a) \\ 0 & sin(a) &...