# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,339 questions
Filter by
Sorted by
Tagged with
24 views

### Turning machines

Consider the language L = {<M1 , M2> | Ǝx such that x ∈ L(M1) ∩ L(M2)} Show that L is not decidable. Im doing a proof by contradiction but im having trouble with the turning machine part
1 vote
22 views

54 views

### What is the complexity of minimising a convex quadratic function over the integers?

The problem of interest is $$\min_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x$$ where $Q$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the ...
29 views

### How to formulate "The general Sudoku problem is in P" formally and rigorously? How to calculate then the input size?

We consider a partially filled starting grid, where $n^2$ is the side size of the grid, $m$ is the number of non-empty initial squares, $f$ is the function that places randomly initially the integers ...
22 views

### Manhattan distance always less node expansion than misplaced tiles heuristic?

I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles. I generated data that said that for a particular random board, misplaced tiles did less node ...
29 views

### Showing for decidable language that is in $P/poly$ but not in $P$ (follow-up)

I've been trying to wrap my head around the proof provided in this answer. I understand that $P$ is a class where languages can be decided by a Turing Machine and that $P/poly$ is a bigger class that ...
61 views

### True or false? Any finite problem is in P

Please explain to me if this is true or false. I had this in an exam, and I really need to know if I got this correct. I believe it is true because finite problems have finite solutions, which can be ...
2k views

### Is there a known polynomial time complexity problem with bad constants?

As you know, big O notation hides all constants. For instance, both runtimes $T_1=n$ and $T_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$). Is there an iconic problem whose best known ...
1 vote
35 views

### Complexity of simulations in simulations

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups. Another example to what I'm referring to, would ...
30 views

### Easy proof of IP ⊆ PSPACE for private coins

There is an extremely standard proof that IP⊆PSPACE, used for instance here, here, or here, by the argument that the full protocol is max-avg game tree that can be evaluated in polynomial space. It's ...
1 vote
104 views

### ( Soft question ) P vs NP - is such a situation possible?

Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements ...
29 views

### Time complexity of search algorithms?

Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ? If so, how do we prove it?
56 views

### Dinitz’ algorithm in simple unit-capacity networks

I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time. This is what is written on the slides ...
24 views

### Optimizing an Algorithm for Timestamp-Aware Partitioning of Data

My Problem I'm currently dealing with an algorithmic problem that involves two input lists: A list of natural numbers $[A_1, A_2, \dots, A_n]$ with $A_1, \dots, A_n \in \mathbb{N}$. A list of triples ...
1 vote
26 views

### Is there any reference materials on complexity analysis for lazy languages?

Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell? I know how laziness is implemented and how it can be expanded and ...
1 vote
45 views

### How to evaluate the complexity of a code

Here is my code for computing the product of sequences of matrices ...
96 views

### Finding all stable matchings in stable marriage problem

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
13 views

### Finding all stable matchings in stable marriage problem [duplicate]

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
48 views

### Reductions to perfect matching

Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
1k views

### Algorithmic Complexity of Recognizing Claw-Free Graphs

Let $H=\left(V_H, E_H\right)$ and $G=(V, E)$ be graphs. A subgraph isomorphism from $H$ to $G$ is a function $f: V_H \rightarrow V$ such that if $(u, v) \in E_H$, then $(f(u), f(v)) \in E$. $f$ is an ...
1 vote
### Is $\Sigma_n^p$-SAT a complete problem for the $\Sigma_n^p$ class with polytime or with logspace reductions?
Here I define $\Sigma_n^p$-SAT to be the problem of deciding if a boolean formula in prenex normal form with $n$ alternating quantifiers, starting with $\exists$, is satisfiable. I found several ...