Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

590 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
377 views

### A simple NP-hard problem

I'm reading this paper, A simple NP-hard problem by Demontis, where he defines an interesting $NP$-hard set and finally he conclude with this theorem: Theorem: $P=NP$ if and only if it is possible ...
43 views

### Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program. I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
41 views

### Volume computation of special polytopes

I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so. I know that in general it is #P-hard to compute the volume of $\mathcal{H}$ -...
67 views

### Unknown gaps in computation models

I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2. where T1 is smaller then T2 and it is unknown if there are problems where their ...
85 views

### Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
49 views

### What is the complexity of Parametric Mixed Integer Linear Programming?

We know $$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$ $$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$ is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference). What is ...
49 views

### Complexity of extending $P_4$-partition of cubic graphs

This is a question I posted on MathOverflow before but never got an answer. I am cross-posting it here. Surprising phenomena occurs when we want to extend a partial solution of some easy problems. We ...
112 views

### What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$. $KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
168 views

167 views

### ExpSpace problems whose configuration reachability problems are in P/poly?

Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly? Let $M$ be an ExpSpace machine. Given two configurations $a$ and $b$ of $M$ (of max length), ...
128 views

### Definition of convex optimization problem by Stephen Boyd and Lieven Vandenberghe

Boyd and Vandenberghe say that a convex optimization problem is one of the form: minimize $f_0(x)$ subject to $$f_i(x)\le 0, i=1,\ldots m$$ $$a_i^\top x=b_i, i=1,\ldots p$$ ...
198 views

### Turing reduction from integer factorization to clique

Is there a general web repository of reductions between and among various NP problems? In particular, I'm looking for a direct Turing reduction from integer factorization (candidate for NP-...
923 views

### How to determine if a function is negligible?

In cryptography (and probably in many other areas) there is a huge usage of negligible functions when proving theorems. Although I know what is a negligible function, every time I encounter a ...
124 views

### Determining if a function is constant or not using period finding

Consider an arbitrary boolean function $$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as: $$f(x_1, x_2 ... x_n)$$ where each $x_i$ is a boolean variable We note ...
126 views

### Computing the period of a function using a quantum computer

Consider a blackbox function $$f(x): Z \rightarrow \lbrace 0,1 \rbrace$$ Which inputs an integer and outputs 0 or 1 with bit complexity n. If the period P of this function satisfies P \in O(2^{...
202 views

### Significance of Logic in Computer Science

I understand the significance of the theory of comptuation, for example NP-hardness of a problem signals us to forget about implementing it's exact solution and rather try approximating it. In the ...
125 views

### Extended Formulaiton and Integer Programming

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints $Ex + Fy = g, y\geq 0$ in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real matrices ...
184 views

### Nonmetric TSP and Functional Compleixty Classes

Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method. Is this general TSP a complete problem in some functional complexity classes ? I'...
112 views

### Complexity of the packing

Let $(A, \leq)$ be a totally ordered alphabet. The packing ${\tt pack(u)}$ of a word $u \in A^*$ is the word of $\lbrace 1, \dots, k \rbrace^*$, where $k$ is the number of different letters of $u$, ...
321 views

### On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

I have 2 questions. Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph ...
348 views

### Maximize Covering Minimizing the Overlap

I have this problem: Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ ...
210 views

### Is there a series of algorithms for approximating TSP polynomially?

I've began studying some CS recently, and I've faced the TSP. The decision problem version of the TSP is NP-complete, right? I've noticed (and elaborated myself) that there exists several polynomial ...
377 views

### Hardness of Happynet problem

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic. What's the reason for this? Are there any related problems, ...
30 views

### Time Complexity of STCONN in One-Tape Turing Machine

I couldn't successfully find relevant work in the time complexity of solving STCONN (in directed graph) in One-Tape Turing Machine. Of course there is a "linear-time" algorithm like DFS/BFS, but is ...
31 views

### Understanding Computability of a Function

I know that computability is the proof of existence of an algorithm to solve a particular function in a infinite time but I can not understand how to decide that it is computable. How can we know ...
17 views

### Vertex k-coloring on Weighted 3-regular Graph allowing Conflict Edges

Given a 3-regular graph with weighted edges (with the signs being positive). Consider the following decision problem: Is there a way to color the the vertices with $k$ colors such that the sum of the ...
144 views

### Complexity class on quantum computation and classic ones

Does the complexity speedup in superpolynomial by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in ...
192 views

### What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...