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)

7
votes
0answers
182 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 ...
7
votes
0answers
207 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 ...
6
votes
0answers
397 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 ...
6
votes
0answers
579 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 ...
6
votes
0answers
488 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 ...
4
votes
0answers
102 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
88 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
52 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
206 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
52 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
52 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
34 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
56 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
81 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 ...
3
votes
0answers
64 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 ...
3
votes
0answers
52 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
38 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
44 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
165 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
201 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 ...
2
votes
0answers
73 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
2
votes
0answers
43 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
36 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
43 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
40 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
40 views

Kleene normal form : elementary?

The Kleene normal form explains there are primitive recursive functions $T$ (a predicate indeed) and $U$ such that for any computable function $\phi_n$, and for any $x\in\mathbb N$ : ...
2
votes
0answers
54 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
82 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
89 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
88 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
95 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 ...
2
votes
0answers
40 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
44 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
38 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
34 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 ...
2
votes
0answers
33 views

Complexity of finding extremal rays

Suppose that $\{L_i\}$ is a collection of $k$ linear forms on $\mathbf R^n$. Let $$C=\{x \in \mathbf R^n : L_i \cdot x \geq 0 \text { for all } i \}$$ be the closed convex cone defined by the ...
2
votes
0answers
62 views

If $P=NP$, prove that $L' \in NP$

I think I'm overthinking this problem and need some hints in the right direction. The goal of this question is to show that if $P=NP$ then for every language $L \in NP$ via a polynomial time verifier ...
2
votes
0answers
22 views

A confusion about RP class of problems

I have some notes which introduces the quantifier $\exists^+x$ and interprets it as "the overwhelming majority of $x$". Then, it defines RP (Randomized Polynomial) as: $$ L\in RP\Leftrightarrow ...
2
votes
0answers
54 views

What makes the permanent lot more difficult than the determinant

The permanent of an $n$-by-$n$ matrix $A$ = $(a_{i,j})$ is defined as: $\operatorname{perm}(A)=\sum\limits_{\sigma\in S_n}\prod\limits_{i=1}^n a_{i,\sigma(i)}$. ...
2
votes
0answers
96 views

Implications of NP=coNP for PSPACE

If NP = coNP, then the Polynomial Hierarchy collapses to its first level (NP). Intuitively, it seems to me that PSPACE should collapse down to NP as well. As a loose heuristic argument, take the ...
2
votes
0answers
74 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 ...
2
votes
0answers
69 views

Asymptotic behavior of $L^2$ norm for increased matrix dimensions

I am playing with matrices which are linear combinations of identity matrix, Pauli spin matrices, $\sigma_x$ and $\sigma_z$ or their tensor products. For example, let the matrix be $H$. So, $H$ could ...
2
votes
0answers
56 views

Why is positional number system natural?

In the theory of computation, one mainly deals with maps $\Sigma^*\rightarrow\Sigma^*$. To discuss computation on other sets $X$ than $\Sigma^*$, one fixes a representation ...
2
votes
0answers
505 views

Solving large, sparse system of linear equations

I have a system of linear equations as follows: $$(A+I)x=B$$ where $I$ is the $n\times n$ identity matrix, $A$ is a $n\times n$ matrix such that the first and last rows are blank, and, for every ...
2
votes
0answers
49 views

Abelian SubGroup Variant:

Consider the following problem: Find integers $x_1, x_2, x_3,\dots, x_n$ Such that: $$P(x_1,x_2,\dots, x_n) = Q$$ for some integer $Q$ and polynomial $P$ where for all permutations of any set of ...
2
votes
0answers
104 views

Solving a particular system of Diophantine equations in $n$ variables (Frobenius equations)

I have a particular system of linear Diophantine equations in $n$ variables for which I need to find all nonnegative integer solutions. Specifically, they are Frobenius equations, meaning the ...
2
votes
0answers
212 views

Polynomial Time Root Extraction

Given a consistent system of polynomial equations: $A_1(x_1, x_2, x_3 ... x_n) = 0$ $A_2(x_1, x_2, x_3 ... x_n) = 0$ etc... $A_n(x_1, x_2, x_3 ... x_n) = 0$ If we let $d_1, d_2, d_3... d_n$ be the ...
2
votes
0answers
110 views

Finding a matching to connect subsets of vertices

I'm studying a graph problem which, strangely, has applications in bioinformatics. I'm not asking for a solution, but rather for advice as to whether something similar to what I do has been studied ...
2
votes
0answers
111 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
2
votes
0answers
118 views

Comparing two character tables

Suppose that you are given two finite groups, for example, via their Cayley tables. One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this ...