Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,330
questions
0
votes
1
answer
14
views
Variant of Bounded Subset Product
Consider the following decision problem:
Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers and $t \le n^c$, do there exists natural numbers $f_1, \cdots f_n$ ...
- 1
0
votes
1
answer
21
views
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
- 1,417
1
vote
0
answers
28
views
What's the intuition behind MIP* being bigger than MIP?
It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.
This was very confusing because it seemed like the (...
- 335
1
vote
2
answers
56
views
Complexity of satisfiability for relational logic on the booleans
I know that propositional satisfiability is NP-complete and that if I add first-order quantifiers I get the complete problems for the polynomial hierarchy and PSPACE. What happens if my formulas are ...
- 2,184
0
votes
1
answer
57
views
Can you compute a majority function of n-bits using an O(n) size circuit?
Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like?
I have a feeling it has ...
1
vote
0
answers
29
views
Complexity class of a problem asking for a chance of receiving an item
I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
- 1,417
1
vote
0
answers
27
views
Lower bounds on max-flow and assignment problems
As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
- 11
0
votes
1
answer
23
views
$NL$ Leaf languages and $PSPACE$
I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505)
20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
- 3
1
vote
1
answer
38
views
Communication complexity of Dyck language
I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
- 11
1
vote
1
answer
59
views
If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine
I found the proof of this theorem from https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf.
Here is the screenshot of the construction of probabilistic Turing machine RP. (https://i.stack....
- 31
0
votes
1
answer
14
views
Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes
I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
-2
votes
0
answers
15
views
Boolean formula in CNF whose conjugtion is NOT satisfiable
Give an example of a Boolean formula which is in CNF form and satisfiable and whose negation is NOT satisfiable.
0
votes
0
answers
13
views
Showing TIME(n) is not closed under poly-time reduction
I am trying to wrap my head around the following proof
Choose some language A $\in$ $TIME(n^3)$ \ $TIME(n)$ (the existence of such a language is guaranteer by the hierarchy theorem)
Let B = {1}
Note ...
- 11
0
votes
0
answers
31
views
An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]
Firstly, we define A and B as two decision problems with the same set of inputs.
Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
- 1
0
votes
0
answers
22
views
Can a problem be NP-complete and also be in complexity class FTP/XP?
P is a NPC problem. Could it be in complexity class XP/FPT or how is the relation to each other?
- 1
0
votes
0
answers
19
views
Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2
If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
0
votes
0
answers
13
views
Given objective value for ILP find parameter is NP hard?
For an integer linear program: Given a matrix $A \in \mathbb{Z}^{n\times d}$ and two vectors $b \in \mathbb{Z}^{n}$, $c \in \mathbb{Z}^{d}$, compute $max\{ c^{\top}x|Ax \leq b, x\geq 0, x\in \mathbb{Z}...
- 101
3
votes
1
answer
53
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 ...
- 133
0
votes
0
answers
25
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 ...
- 9
0
votes
0
answers
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 ...
0
votes
0
answers
27
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 ...
- 11
-4
votes
1
answer
60
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 ...
15
votes
4
answers
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
1
answer
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 ...
2
votes
0
answers
29
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 ...
- 923
0
votes
2
answers
96
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 ...
0
votes
1
answer
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?
- 101
2
votes
1
answer
55
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 ...
0
votes
0
answers
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
0
answers
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
0
answers
40
views
How to evaluate the complexity of a code
Here is my code for computing the product of sequences of matrices
...
- 111
0
votes
0
answers
90
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 ...
- 1
0
votes
0
answers
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 ...
- 1
0
votes
1
answer
44
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 ...
- 1
7
votes
2
answers
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 ...
- 303
1
vote
0
answers
19
views
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 ...
- 31
0
votes
1
answer
33
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
1
vote
1
answer
45
views
GNI public coin interactive proof: why randomize y?
I've read this scribe that provides a public coin interactive proof for graph non-isomorphism.
In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
- 11
0
votes
0
answers
26
views
If $NP \ne coNP$, $L_1, L_2 \in NP$, then is it necessary for $\bar{L_1} \cap L_2 \in NP$ and checking the proof of $P \ne NP$
I am a beginner in the computer science track.
I have some problems with the following problems
Problem 1: Assume that $NP \ne coNP$. If $L_1, L_2 \in NP$, is $\bar{L_1} \cap L_2$ necessarily in $coNP$...
- 1
0
votes
0
answers
23
views
Greedy algorithm for minimising the number of encountered obstacles from multiple start points to single endpoint in a grid
I am given a $N$ x $M$ sized grid and $K$ start points $S = (s_1, s_2, .. s_k)$ where each $s_k = (x_k,y_k)$ representing the position on the grid. I am also given a single endpoint $(x_{end}, y_{end})...
- 141
0
votes
1
answer
26
views
Minimizing the number of distinct elements by picking one set from each set of sets
I have a problem as follows. Given a set of sets $U = \{S_1, S_2, … S_N\}$ where $S_i = \{s_1, s_2, ... s_m\}$. Each $s_j \in S_i$ contains a set of distinct elements. I need to pick one $s_j \in S_i$ ...
- 141
1
vote
1
answer
36
views
Maximum Weighted coverage approximation algorithm?
I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version.
How should I modify the algorithm above to ...
- 141
0
votes
1
answer
31
views
How big is a formula equivalent to a wff over $n$ variables with $2^n$ subformulas?
Definitions: Let $n \in \mathbb{N}$. If $\alpha$
and $\beta$ are propositional formulas,
then we'll call $\alpha$ and $\beta$ independent if neither implies the other,
or more formally, if $\lnot (\...
- 923
0
votes
1
answer
47
views
Is there any example of a Turing-recognizable language mapping reducible to a NOT Turing-recognizable language?
Theorem: "If A is mapping reducible to B and B is recognizable, then A is recognizable."
I know that the following statement is FALSE.
"If A is mapping reducible to B and A is ...
0
votes
1
answer
16
views
How does the sumcheck protocol help solving the #SAT (circuit satisfiability) problem?
I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf - "Proofs, Arguments, and Zero-Knowledge"
He presents the Sumcheck protocol & then ...
- 125
1
vote
0
answers
12
views
Computation of composition of analytic functions [closed]
There are several algorithms available for computing the approximate values of functions. These can involve methods like the arithmetic-geometric mean or the Taylor series. Given a set of analytic ...
- 11
0
votes
0
answers
6
views
Circuit Complexity Query regarding the minimum circuit size and input size range
Given a boolean function it can always be represented by a family of circuits.
Query 1: Is it true that, for any integer $N$ and for all $I_{in}$ such that $I_{in} \leq 2N$
There exists a circuit of ...
- 753
1
vote
1
answer
113
views
Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time
I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
- 83
1
vote
0
answers
84
views
complexity of graph matching with order constraint
Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$.
Find the maximum $k$ such that ...
- 11
0
votes
1
answer
41
views
how do universal turing machines actually work
a TM has states and a tape, and a set of symbols that can get put on the tape. when it 'reads' a symbol on the tape, it's current 'state' tells it what to do next; write a new symbol, where to move ...
