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)

10
votes
0answers
250 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 ...
9
votes
0answers
521 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 ...
7
votes
0answers
190 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
6
votes
0answers
53 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 ...
6
votes
0answers
195 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
6
votes
0answers
524 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
5
votes
0answers
116 views

Philosophical implications of P vs NP proof?

Wikipedia article on P vs NP says that "a proof either way would have profound implications for ... Philosophy" without providing further details. So I was wondering what could be the philosophical ...
5
votes
0answers
108 views

Is it decidable whether the iterates of a polynomial map are bounded?

Let $f:\mathbb{Q}^n\to \mathbb{Q}^n$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
4
votes
0answers
91 views

How to efficiently calculate $ax+b$ once I know $a$ and $b$?

What's the cheapest way to calculate $ax+b$ several times once I know the values for $a$ and $b$? For instance, the cheapest way to calculate $ab+x$ several times once I know the values for $a$ and ...
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 ...
4
votes
0answers
227 views

Proving NP-completeness (hardness) exercises

I am looking for a list of exercises that can be done to practice polynomial time reductions to prove NP-hardness of problems. I know there are hundreds (thousands?) of problems proven to be NP-hard. ...
3
votes
0answers
44 views

Can these definitions of the words “problem” and “solution” be formalized, and if so, has this been done? If so, where can I learn more about it?

I had a thought. Define that: Vague Definition 0. A problem consists of: a set $X$ a set $Y$ a function $f : X \rightarrow Y$ a way $\overline{X}$ of representing the elements of $X$ ...
3
votes
0answers
48 views

Is it faster to calculate inverses of symmetric matrices as opposed to asymmetric matrices? How?

I know there are several methods to inverse or decompose matrices. I am looking for a comparison of the computational cost of inverting an arbitrary real, symmetric matrix vs a real, asymmetric one. ...
3
votes
0answers
71 views

The role of the extraction matrix in a Kalman filter

The extraction matrix shown as $H_k$ below, transforms the state vector into a form that can be subtracted from the measurements vector: $\hat{X}_k = \hat{X}_k^- + K_k ({z}_k - H_k \hat{X}_k^-)$ ...
3
votes
0answers
27 views

Complexity Of Recognising Complete Multipartite Graphs

Short question: Is there a linear time algorithm for recognising complete multipartite graphs?
3
votes
0answers
38 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 ...
3
votes
0answers
65 views

Asymptotic running time for multiplying multivariate polynomials using Schönhage/Strassen

Question: I would like to ask the community where my following suggestion for an asymptotic bound for the running time of multiplying two multivariate polynomials using theorem $8.23 $ recursively ...
3
votes
0answers
69 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
3
votes
0answers
60 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
3
votes
0answers
94 views

On the equidistant distribution of $n$ points on a sphere $S^2$ by algorithm and their “validity” measures by statistical methods

I have found an algorithm for distributing $n$ points $P_0, P_1, ..., P_n$ (approximately) equidstantly on a sphere where $$\varphi_i = \pi(\phi - 1)i \qquad \theta_i= \mathrm {asin} (2i/n - 1), ...
3
votes
0answers
86 views

Category theory and complexity classes

Is there any interesting way to make the set of computational complexity classes into a category? Almost every interesting mathematical class of objects forms a category after all.
3
votes
0answers
223 views

Complexity analysis of convex optimization problem

I am studying an optimization problem \begin{equation} \mathbf{x}^*=\text{argmax}\quad\sum_{d=1}^{D}\log(\mathbf{a}_d^T\mathbf{x}+b)+\mathbf{c}_d^T\mathbf{x}+f_d\\ \text{subject to}\quad ...
3
votes
0answers
85 views

Plot implicit equation in sub-quadratic time complexity

It is fairly straightforward to plot an explicit equation such as $y=x^3+3x^2+2x+5$ in linear time, because you can just iterate through all $x$ in your graphing space and use the equation to ...
3
votes
0answers
43 views

Examples of functions which grow faster than their computational complexity.

A good example of this would be the function $f$ defined as follows, $f(n) = (10^n-1)$. While in this form it's equation is exponential, it is easy to note that $$f(n) = 99...9 \,(n \text{ times}).$$ ...
3
votes
0answers
60 views

Period of a multivariable function

consider a function $$f(x_1, x_2, \ldots, x_n) $$ is it possible to compute the period of the function as a vector $$\langle l_1, l_2, \ldots, l_n\rangle$$ where each $l$ denotes the period of the ...
3
votes
0answers
216 views

$\sum _{i=1}^{n} \sum _{j=1}^{n} \sum _{k=1}^{n}\sum _{l=1}^{n} A(i,j)A(i,k)A(i,l)A(j,k)A(j,l)A(k,l) $

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(i,j)A(j,k)A(k,i)$, where A(i,j) is the a ...
3
votes
0answers
224 views

Amortized Analysis for (2,5)-Tree

I need some help with the following problem Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 ...
3
votes
0answers
297 views

Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
2
votes
0answers
39 views

Fast algorithm to recognize sortable sequences

Every sequence is sortable in the worst-case by a $O(n^2)$. However, if we restrict sorting primitive, we get an interesting problem. I am interested in this sorting problem: Input: a sequence $A$ of ...
2
votes
0answers
76 views

Relationship between Complexity and Computability

As a response to comments,i'd like to put it in an abstract way,hoping this will make things clearer: f is a well-defined function of countably many inputs:f(a1,...,an,...). For a set of n objects ...
2
votes
0answers
32 views

Calculating time complexity of an algorithm.

In the chapter Algorithm Analysis of the book Algorithm Design Manual there is an example of string matching algorithm, I am typing the partial code below: ...
2
votes
0answers
30 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
2
votes
0answers
33 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
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( ...
2
votes
0answers
10 views

Complexity notation (Omega) consequence

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$ But is this always true ? I couldn't come up with a ...
2
votes
0answers
76 views

Fastest way to find linearly independent columns of a matrix

Given a rectangular matrix $X$ of size $n\times m$ with $m>n$, what is the fastest way to find the linearly independent coloums. Robust methods like SVD or RRQR decompostion have complexity of ...
2
votes
0answers
81 views

A question on GCT

In http://ramakrishnadas.cs.uchicago.edu/gctriemann.ps it is stated that there is an unknown non-standard riemann hypothesis. AFAIK riemann hypothesis in AG was shown using Etale cohomology by Artin, ...
2
votes
0answers
98 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
0answers
48 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
2
votes
0answers
50 views

Book or paper recommendation about “Rube Goldberg Mathematics” // e.g. Longest path problems

First: My question is not be very specific, since I lack a concrete overview, but my idea/thoughts in a nutshell: I would like to have a recommendation of a good book, paper or article about processes ...
2
votes
0answers
53 views

how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
2
votes
0answers
59 views

Is there a plausible outline of how geometric complexity theory could prove $P \neq NP$?

I've heard people saying that geometric complexity theory could be the key to showing $P \neq NP$, but when I've actually read about it it seems like it's concerned with other, perhaps analogous ...
2
votes
0answers
136 views

Datermine the time complexity of an algorithm calculating the sum of Euler $\phi$ function.

Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function. The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$. For simplify, I'd ...
2
votes
0answers
122 views

Computing a “cheap” upper bound on the norm of the solution to a linear system

Consider the linear system $A x = b$, where $A$ is an invertible, $n \times n$, real matrix. I would like to compute a "cheap" upper bound on the (p-)norm of the solution; i.e. $\|x\|_p$. One can, of ...
2
votes
0answers
96 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
2
votes
0answers
70 views

Could any one explain the difference between the theorems?

In the paper http://annals.math.princeton.edu/2007/165-2/p04 Theorem 2. Let $b \ge 2$ be an integer. The b-ary expansion of any irrational algebraic number cannot be generated by a finite automaton. ...
2
votes
0answers
50 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
2
votes
0answers
50 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
2
votes
0answers
44 views

Is there any oracle A s.t. NP$^A$ $\neq$ EXP$^A$

I think the answer is yes because we do not know whether NP = EXP. But i couldn't find one.
2
votes
0answers
35 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...