# Questions tagged [computational-complexity]

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

1,052 questions
Filter by
Sorted by
Tagged with
47 views

### Number of solutions to linear diophantine equations, with natural coefficients in a box

Let c, k, d $\in \mathbb{N}$, let a, x $\in \mathbb{N}^k$ suppose for all i $\leq$ k, $x_i \leq d$, $a_i \in \mathcal{O}(d2^i)$ and $\sum{a_ix_i} = c$ my question is for the value of c ...
109 views

### Integration modulo integers

$f(x,\theta)=\frac{g(x,\theta)}{h(x,\theta)}$ be a function parametrized by $x\in\mathbb N$ such that its integral with $\theta\in[a,b]$ for fixed $a,b\in\mathbb R$ is always an integer. The ...
30 views

### A quasi-polynomial time PTAS for a MAX SNP-hard problem implies that $NP \subseteq QP$

I'm reading a paper [Jiang, Tao; Li, Ming; On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24 (1995), no. 5, 1122–1139.] with some non-...
67 views

### Computational complexity in linear solvers

I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $\mathit{inv}$ under certain if-conditions to obtain ...
38 views

### Gröbner basis and integer programming

I was studying about grobner basis and observed one application of it in integer programming which is pretty much amazing but tougher than available methods like branch bound. Then what is the benefit ...
61 views

### Computational complexity of computing the trace of a matrix product under some structure

I have two problems related to computing some trace, and some (possibly suboptimal) answers. My question is about a potential more efficient algorithm for each one. (More interested in an answer to ...
85 views

112 views

93 views

### Is integer circuit membership undecidable?

According to wikipedia integer circuit in its simplest form is succinct representation of multivariate polynomial with integer coefficients. Decidability if an integer is represented by the integer ...
145 views

### Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]

Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
There is a set of vectors $\vec a_{k,i}$ with $k\in\{1,\dots,n\}$ and $i\in\{0,1\}$, such that every $n+1$-tuple $\{\vec v_{1,s_1},\dots,\vec v_{n,s_n},\vec v_{r,1-s_r}\}$ is linearly independent for ...
Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan. $X_P$ is always projective, because the collection of characters corresponding to the points \$\...