# 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,262 questions
Filter by
Sorted by
Tagged with
11 views

### Convergence bound for zero-order optimization method

I would like to understand the error bound for a particular zero-order optimization method: (stochastic) difference method. To solve an nonsmooth optimization problem $min_x G(x)$ where $G$ is only a ...
195 views

### MIP*=RE theorem and its impact on logic and proof theory

In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
1 vote
37 views

### Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed. With the two (related) examples, it is clear that ...
1 vote
33 views

### Are the lower elementary functions closed under limited recursion?

The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
75 views

105 views

### Optimization over permutation

The Problem This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
1 vote
82 views

### Computing sine of gamma function

In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step? Is there a ...
50 views

### Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
19 views

### Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?

I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
46 views

### On diagonalizations over complexity classes

I am looking for the following PhD thesis, but could not find it, and all my attempts for finding it failed. I am wondering if there is a way to get it: On diagonalizations over complexity classes By: ...
39 views

### Complexity for determining whether a given metric space is hyperconvex?

Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex? Definition: A metric space is said to be hyperconvex if ...
58 views

### Complexity of continued fraction arithmetic operations

Let $A = [a_0; a_1, \dots]$ and $B = [b_0; b_1, \dots]$ be continued fractions. Let's say that we want to compute $A+B$ or $A \cdot B$ while staying in the continued fraction representation. So, for ...
110 views

### The counterpart of productive set with polynomial computational complexity

For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...
710 views

### Equivalence between deterministic and non-deterministic counter net

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
356 views

### Classes of groups with polynomial time isomorphism problem

It is known that the isomorphism problem for finitely presented groups is in general undecidable. What are some classes of groups whose isomorphism problem is known to be solvable in polynomial time? (...
510 views

### Counter net decidability [closed]

Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...