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)

80
votes
4answers
2k 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}}}}} < ...
48
votes
4answers
4k views

Is “A New Kind of Science” a new kind of science?

A couple of years ago I was reading "New Kind of Science" (NKS) by S. Wolfram, and it presented lot of interesting ideas for a young Physics undergraduate. Now that I am studying Mathematics however, ...
32
votes
4answers
858 views

What is the *middle* digit of $3^{100000}$?

The decimal representation of $3^{100000}$ has $47713$ digits. What is the $23857^{th}$ digit - i.e. the one in the $10^{23856}$'s place? There are lots of questions on this site asking for the last ...
30
votes
1answer
2k 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. ...
29
votes
2answers
3k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
20
votes
3answers
751 views

Complexity of computing $ABx$ depends on the order of multiplication

To calculate $y = ABx$ where $A$ and $B$ are two $N\times N$ matrices and $x$ is an vector in $N$-dimensional space. there are two methods. One is to first calculate $z=Bx$, and then $y = Az$. This ...
16
votes
2answers
1k 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 ...
15
votes
1answer
13k 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 ...
13
votes
1answer
995 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
13
votes
3answers
817 views

Must an algorithm that decides a problem in NP also produce a solution?

I think I have a basic misunderstanding in the definition of a decision problem. It's widely believed that a proof of P=NP would break all modern cryptography, for example:- http://security....
12
votes
4answers
3k 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 ...
12
votes
1answer
9k views

Computational complexity of least square regression operation

In a least square regression algorithm, I have to do the following operations to compute regression coefficients: Matrix multiplication, complexity: $O(C^2N)$ Matrix inversion, complexity: $O(C^...
12
votes
3answers
327 views

Efficient computation of $E\left[\left(1+X_1+\cdots+X_n\right)^{-1}\right]$ with $(X_i)$ independent Bernoulli with varying parameter

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$ ...
12
votes
3answers
341 views

Eigenvalue test faster than $O\left(n^3\right)$?

Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm. Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's ...
12
votes
1answer
278 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
11
votes
3answers
325 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 ...
11
votes
1answer
620 views

Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
11
votes
3answers
140 views

How does one interpret statements like: “The traveling salesman problem is NP-complete?”

The world abounds with statements like: The traveling salesman problem is NP-complete. But when I follow try to follow the Internet's links "down the rabbit hole," I don't get a truly sensible ...
11
votes
2answers
325 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
11
votes
4answers
716 views

Is there an easy way to find the sign of the determinant of an orthogonal matrix?

I just learned that if a matrix is orthogonal, its determinant can only be valued 1 or -1. Now, if I were presented with a large matrix where it would take a lot of effort to calculate its determinant,...
11
votes
1answer
225 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 ...
10
votes
4answers
663 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 ...
10
votes
2answers
933 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 ...
10
votes
2answers
802 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 ...
10
votes
1answer
315 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 ...
10
votes
1answer
539 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
2answers
271 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 \...
10
votes
3answers
207 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
10
votes
1answer
159 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 ...
10
votes
1answer
310 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 ...
10
votes
0answers
255 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 ...
10
votes
0answers
548 views

Is there a theory that combines category theory/abstract algebra and computational complexity?

Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't ...
9
votes
2answers
989 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 ...
9
votes
5answers
567 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 ...
9
votes
1answer
1k 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 ...
9
votes
1answer
4k 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 ...
9
votes
2answers
267 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
9
votes
1answer
444 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}}} \...
9
votes
2answers
2k views

If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
9
votes
1answer
153 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
8
votes
2answers
1k 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 ...
8
votes
1answer
792 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. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
8
votes
1answer
1k 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 \sqrt{x}...
8
votes
1answer
269 views

Applications of computation on very large groups

I have been studying computational group theory and I am reading and trying to implement these algorithms. But what that is actually bothering me is, what is the practical advantage of computing all ...
8
votes
1answer
161 views

Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields?

My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few ...
8
votes
1answer
13k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
8
votes
1answer
506 views

efficient summation of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a $i$...
8
votes
2answers
110 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 "yes,...
8
votes
1answer
207 views

Cholesky of Matrix plus Identity

I have a positive definite matrix $A$ ($n \times n$ dimension) for which I have the Cholesky decomposition $A=LL^{'}$. I want to use this to compute a) The cholesky decomposition of $A+c^2\times I $ ...
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 ...