Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

6
votes
0answers
177 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
255 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
422 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
66 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 ...
5
votes
0answers
511 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 ...
5
votes
0answers
331 views

how can i prove that square root of n is space constructible

I know that square-root of n is space-constructible. I can't prove it by the space-constructible definition. How can I show that only $\sqrt{n}$ space is used?
4
votes
0answers
76 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
71 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 $a+b+x$ several times once I know the values for $a$ and ...
4
votes
0answers
136 views

Connect 4 - SAT

My question is about how the Hasbro game Connect4 can be viewed as a SAT problem. My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is ...
4
votes
0answers
171 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
30 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
38 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
48 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 ...
3
votes
0answers
139 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
173 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
39 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
37 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
30 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
21 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
17 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
70 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
60 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
48 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
80 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
160 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
87 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
97 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
102 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 ...
2
votes
0answers
202 views

Pseudo inverse of matrix: SVD vs $A^{T}(A.A^{T})^{-1}$

For a C++ implementation I have to calculate Moore Penrose Inverse (AKA pseudo inverse) of non squared matrices. I was wondering ...
2
votes
0answers
67 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
2
votes
0answers
228 views

$NP$-completeness of scheduling problem

I have been attempting to show that this problem is NP -complete but haven't been successful. I wonder if anyone has a suggestion for a problem I could reduce to it. CALLS : Suppose we have nodes ...
2
votes
0answers
177 views

What is the computational complexity of the EM algorithm?

In general, and more specifically for Bernoulli mixture model (aka Latent Class Analysis).
2
votes
0answers
22 views

complexity of time constructible function

In field of computational complexity there is a definition of time constructible function. As example, in any reasonable and general model, functions like $t_1(n) = n^2, t_2(n) = 2^n$, and $t_3(n) = ...
2
votes
0answers
37 views

How would you write this sentence

I'm writing a short document about an integer programming (IP) problem instance. I've mentioned that IP is known to be NP-Hard, but that being NP-Hard doesn't automatically qualify this particular ...
2
votes
0answers
113 views

matrix construction

Given any matrix $A$, can one construct a matrix $B$ such that $B$ is nonnegative and the spectral radius of $B$ is strictly less than 1 the determinant of $A$ is equal to the first entry of $B^*$ ...
2
votes
0answers
124 views

reducing #P-complete problem to NP problem

What would be the consequence and meaning of existence of polynomial reduction of #P-complete problem into NP problem (not NP-complete problem)?
2
votes
0answers
162 views

2-Player Game PSpace-Completeness

So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more ...
2
votes
0answers
66 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
2
votes
0answers
159 views

Complexity of finding all edge cuts of a directed graph

I have a problem in which for a certain graph I need to compute the min cut for r times (r can be HUGE). Because each time the edge weights can be different, what i am doing (in practice) is to ...
2
votes
0answers
108 views

Complexity of map coloring

This is a follow up question to this one. I've recently read that for planar maps, it is possible to color these in $O(N^2)$, $N$ being that number of vertices [1]. What are the computational ...
2
votes
0answers
261 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 ...
1
vote
0answers
24 views

Is finding a matrix out of some set with a given determinant a hard problem?

Given $n\ge 2\ \ ,\ u,v,k\ $ integers. Decision problem : Does a $n\times n$ - matrix with entries from $u$ to $v$ with determinant $k$ exist? In which complexity class is this problem ? Is it ...
1
vote
0answers
47 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
0answers
55 views

GCD of high order polynomials(modulo large prime)

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
1
vote
0answers
25 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$ ...
1
vote
0answers
16 views

Find a simple Theta bound for a geometric series

I'm working on a question like: find a simple g(n) (big theta) for $ f(n) = \sum _{i=1}^n 5^i $ My working starts with this $\frac{5-5^n}{1-5}$ which is not equivalent to the correct answer from ...
1
vote
0answers
25 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
0answers
52 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
1
vote
0answers
25 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
1
vote
0answers
30 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...