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
1answer
39 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 ...
1
vote
0answers
27 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 ...
0
votes
1answer
29 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
27 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
27 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
175 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
66 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
268 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
48 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
40 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
56 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
171 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
73 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
58 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
62 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
72 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
126 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
27 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 ...
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
256 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) ...
1
vote
1answer
35 views

How do we decide a problem is in NP, but not in P or NPC?

As I understand, NPC set contains only the problems which can be polynomially converted into each other and which are hardest in NP set/ But how do we decide which problems are in NPC and which ...
0
votes
0answers
45 views

nocomputable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
4
votes
1answer
184 views

Giving tight asymptotic bounds for $T(n)=T(\frac{n}{\log n}) + \log\log n$

I don't like coming here for such matters, but this is a homework problem from my Analysis of algorithms class. I've come along the Akra-Bazzi method and different variations on the matter , read ...
0
votes
1answer
52 views

not any computable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
5
votes
1answer
64 views

Is there a number $n$, such that there are $22$ groups of order $n$?

Denot : $N(n)$ : the number of groupfs of order $n$ ? Is there a number $n$ with $N(n)=22$ ? Checking the first about $2000$ numbers, I noticed that there is no $n\in [1,2000]$ with $N(n)=22$. ...
0
votes
0answers
19 views

How to devise an efficient algorithm to detect if every cycle of a weighted graph has, at least, two edges with the maximum weight

Let M be an adjacency matrix representing a weighted graph G. I'm trying to devise an algorithm to verify if, for every cicle C of G, the edge with biggest weight of C is not unique on C. I can think ...
3
votes
0answers
39 views

Is the problem : Determine the number of groups with order $n$ NP-hard?

It can be hard to determine the number of groups with order $n$, especially for $n=2^k$. So, I wonder, whether there is a polynomial algorithm doing this. I think, this is not the case because for ...
0
votes
1answer
20 views

How to start dealing with this recurrence relation

I have never seen a recurrence in this form, so I don't know how to proceed. I'm supposed to find asymptotic bounds (preferably $\Theta$(something)) for: $$T(n) =T\bigg(\frac{n}{\log n}\bigg)+ \log ...
1
vote
1answer
57 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
2
votes
1answer
84 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random ...
0
votes
0answers
18 views

Computational Complexity of exponentiating

I'm currently studying this paper and I am trying to understand the complexity of the interpolate algorithm, which is supposed to be $O((l+m)^2)$. So first the algorithm runs in $r$ steps where ...
0
votes
1answer
24 views

The approximability of different NP-hard problems

I'm fairly new to the topic Computational Complexity and had the following question (I therefore apologies before hand for any poorly stated terminology). Suppose i have two optimization problems ...
0
votes
1answer
26 views

Asymptotic complexity of power of logs

I'm trying to simplify $\Theta(lg^k(n/2))$. I believe it's $\Theta(lg^kn)$ but i don't know if the following proof is correct... i'd love to receive some input I tried doing - ...
0
votes
0answers
14 views

Np-hardness of a problem related to the knapsack problem

I am trying to know whether the following problem is NP-hard: Input: A positive number k and N pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
3
votes
1answer
44 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...