Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

6
votes
0answers
163 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
56 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
219 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 ...
5
votes
0answers
484 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
308 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?
5
votes
0answers
398 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
128 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
160 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
27 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
37 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
42 views

What is the simplest collatz like problem that is undecidable?

I have read that problems resemblings collatz have been shown to be undecidable. Conway proved that apparantly but Im not sure if the proof was constructive. So I wonder : What is the simplest ...
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
133 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
164 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
27 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
18 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
15 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
64 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
58 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
45 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
72 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
138 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
80 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
90 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
95 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
141 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
62 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
212 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
161 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
108 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
115 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
153 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
62 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
145 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
101 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
243 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
11 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.
1
vote
0answers
64 views

Necessary and sufficient conditions for $\rm P \neq NP$ maybe?

Please review the $\rm P \neq NP$ problem here. I'm working on an algebraic approach to this problem, and all my notes are currently here. Conjecture 1 For all $f \in F[x_1, \dots, x_k]$, a minimal ...
1
vote
0answers
27 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 ...
1
vote
0answers
41 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 ...
1
vote
0answers
38 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
1
vote
0answers
37 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)}$. ...
1
vote
0answers
35 views

What is the difference between the Big O and Big O star (asterisk) operator?

I'm doing some research on algorithms complexity and in different papers I notice both the use of the regular Big-O operator O(...) and a variant ...
1
vote
0answers
31 views

Computational Complexity

I have no interest in computational complexity theory. Well I should say, mathematics is interesting, rather that, I find myself doing other stuff and never learned anything about CCT. My question ...
1
vote
0answers
39 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 ...
1
vote
0answers
34 views

Is Quadratically Constrained Quadratic Program (QCQP) in NP?

The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity? If the general version of QCQP ...
1
vote
0answers
30 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
1
vote
0answers
70 views

A question on the computational complexity of Boruvka's algorithm

One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm). On the page you would see once you clicked ...