Computational complexity, a part of theoretical computer science.
49
votes
4answers
1k views
Complexity class of comparison of power towers
Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
17
votes
1answer
1k views
$e^{e^{e^{79}}}$ and ultrafinitism
I was reading the following article on Ultrafinitism, and it mentions that one of the reasons ultrafinitists believe that N is not infinite is because the floor of $e^{e^{e^{79}}}$ is not computable. ...
15
votes
2answers
914 views
What is the complexity of succinct (binary) Nurikabe?
Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
11
votes
4answers
841 views
Can an algorithm be faster than O(1)?
This week we had a bright interviewee who claimed that array has constant search time and map has even faster than that search time. Now to me if some algorithm has O(1) time complexity the only way ...
11
votes
3answers
274 views
Efficient computation of $E\left[\frac{1}{1+\sum_iX_i}\right]$ where $X_i$ is RV with Bernoulli distribution with different probabilities
Suppose we have the random variables $X_1, \ldots, X_n$ that have Bernoulli distributions with the (possibly different) probabilities $p_1, \ldots, p_n$. For example, $X_1$ = 1 with probability $p_1$ ...
10
votes
1answer
292 views
Algorithm for a deck manipulation
Let's say you have a randomised deck of $N$ different cards. An $M$-action ($M\le N$) is defined as follows: you look at the top $M$ cards of the deck, put as many of them as you choose on top of the ...
10
votes
1answer
206 views
How can I intuit the role of the central limit theorem in breaking the curse of dimensionality for Monte Carlo integration
I would like to more intuitively understand where the power of Monte Carlo integration comes from for large-dimensional domains of integration.
Other questions on this site have referenced the proof ...
9
votes
2answers
231 views
An interesting way of producing positive integers
If we define $$\cal N _1 := \{ 1\} $$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$
it's easy to prove that, for every $m ...
8
votes
4answers
326 views
If $P \ne NP$, is every language not contained in $NP$ $NP$-hard?
The other day, a student asked me whether, if $P \ne NP$, whether any language outside of $NP$ is known to be $NP$-hard. I wasn't sure if
This is definitely known to be true,
This is definitely ...
7
votes
3answers
132 views
Why isn't NP = coNP?
Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
7
votes
2answers
266 views
How hard is it to do arithmetic?
People in computing are often observed saying that a computation takes $\operatorname{O}(n^3\log n)$ steps or that it's NP-hard or that it's not computable, or that it's primitive recursive, etc. I ...
6
votes
2answers
345 views
Two $NP$-complete languages whose union is in $P$?
I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in ...
6
votes
2answers
249 views
Do there exist exponential-time problems, even if $P=NP$
Can we say that there are some problems that take exponential time even if $P=NP$
For instance problems like: enumerating all spanning trees of a graph, enumerating all hamiltonian paths of a graph, ...
6
votes
2answers
487 views
Has there been a rigorous analysis of Strassen's algorithm?
According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java?
I ...
6
votes
1answer
209 views
Could someone prove they had a halting oracle?
Suppose someone comes to you and claims to have a halting oracle. Is there any way for you to verify the truth or falsity of their claim in finite time? If so, what constraints on the proof process ...
6
votes
2answers
384 views
Optimization Puzzle
You are given a large number of LEGO blocks of size 1. You can build blocks of other sizes using smaller blocks. For example, you can build a block of size 2 using two of size 1 blocks and then build ...
6
votes
1answer
810 views
Definition of time-constructible function
What would be an intuitive notion of time-constructible functions ? Is there a function which is not time-constructible?
In my own words I would say a function is time-constructible when 1. it is ...
6
votes
1answer
751 views
What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?
I looked it up online in many sites but none give a clear answer. They all give a lot of complicated mathematical stuff which is not only hard for me to grasp but also irrelevant as I simply want to ...
6
votes
1answer
318 views
Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$
I was reading about Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$ by ultrafinitists.
I am wondering if they were to deny the existence of $\lfloor e^{e^{e^{79}}} ...
6
votes
1answer
52 views
Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?
I want to write a function that does the following:
Input:
An integer $n$
A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets ...
5
votes
4answers
403 views
Does DTIME(O(n)) = REGULAR?
(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to ...
5
votes
2answers
99 views
Time complexity - Why does doubling the speed given this improvement?
Hi I've been studying time complexity recently and I'm really confused about something I've come across.
The problem
Suppose we can solve a size n problem instance in 1 hour. If we double the ...
5
votes
2answers
173 views
Computing nth term of fibonacci-like sequence for large n
Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach:
$$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$
...
5
votes
1answer
236 views
What is the significance of the graph isomorphism problem?
It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
5
votes
1answer
115 views
What is wrong with this decision procedure for 3SAT?
So I came up with a decision procedure for 3SAT which would seem to be completeable in a polynomial amount of time. Naturally, I am assuming it is incorrect, but I don't know where the mistake is.
...
5
votes
1answer
716 views
Complexity of counting the number of triangles of a graph
The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle.
This procedure ...
5
votes
2answers
225 views
Is there a log-space algorithm for divisibility?
Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
5
votes
1answer
85 views
Simplify $O(n^k/2^n)$
In one of my complexity analysis, I came up with $O(n^k/2^n)$, where $k$ is a fixed number and $n$ is the size of the data. However I rarely see a big-O written as this. Is there a way to even further ...
5
votes
1answer
108 views
Complexity of finite group isomorphism problem
Consider the next decision problem:
Given two finite groups represented by their multiplicity table, determine if they are isomorphic or not.
Clearly, this problem belongs to NP since given a witness ...
5
votes
1answer
459 views
Why are Hornsat, 3sat and 2sat not equivalent?
I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
5
votes
2answers
94 views
Understanding the Pumping Lemma
I have been having an extremely hard time proving a language is irregular using the pumping lemma. I looked and dozens of examples and spent hours on this one topic, and I am still not able to wrap my ...
5
votes
1answer
177 views
Is there an efficient algorithm to compute a minimal polynomial for the root of a polynomial with algebraic coefficients?
An algebraic number is defined as a root of a polynomial with rational coefficients.
It is known that every algebraic number $\alpha$ has a unique minimal polynomial, the monic polynomial with ...
5
votes
1answer
187 views
Precision and performance of Euclidean distance
The usual formula for euclidean distance that everybody uses is
$$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$
Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical ...
5
votes
1answer
239 views
Can a Pratt certificate for a prime be found in polynomial time?
Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
5
votes
1answer
51 views
Maximal Zero Sums Partition
You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
5
votes
0answers
87 views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
5
votes
0answers
368 views
The Average Running Time Of Euclid Algorithm?
What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?
It seems very hard to deduce from the recurrence
$T(m,n) = T(n, m ...
4
votes
3answers
2k views
Worst case complexity of the quicksort algorithm
Good evening,
I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
4
votes
3answers
733 views
Proof Hampath is NP-Complete
I'm really confused by the proof that Hampath is NP-Complete. In order to prove something is NP-Complete, we can reduce another NP-Complete problem to it. So we want to take 3-SAT and reduce it to ...
4
votes
1answer
245 views
Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?
I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this:
Strassen’s algorithm is not at all obvious. (This might be the biggest ...
4
votes
3answers
254 views
How complicated is the set of tautologies?
Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$.
How ...
4
votes
2answers
71 views
Minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
4
votes
2answers
176 views
Is there a function that only generates primes?
The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$?
I'm having difficulty specifying exactly what I want "nice" to mean, ...
4
votes
2answers
232 views
What is the relationship between ZFC and Turing machine?
I did not learn Logic properly but so far I understand that proof systems can be viewed as a kind of machine. For proof system, ZFC seems to be the most powerful one that we use so far. Similarly, for ...
4
votes
2answers
623 views
Subset sum problem is NP-complete?
If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
4
votes
1answer
251 views
Divisor summatory function for squares
The Divisor summatory function is a function that is a sum over the divisor function.
$$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor ...
4
votes
1answer
104 views
Primality Testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$?
What is known about the computational complexity of primality testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ where $d$ is a square-free number? For what values of $d$ is primality testing easy ...
4
votes
1answer
95 views
Issue while applying Master Theorem
I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...
4
votes
3answers
95 views
What would be complexity of computing $3^{n^n}$?
Just curious, what would be the computational complexity of computing $3^{n^n}$?
I am not sure what it would be like.
4
votes
2answers
203 views
Time complexity to calculate a digit in a decimal
As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a ...
