Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,339
questions
-1
votes
0
answers
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
1
vote
1
answer
22
views
Polynomial Hierarchy - the difference between $\Pi$ and $\Sigma$
The way I understand is that complexity classes which are denoted with $\Sigma_i$ are representing a combination of alternating variable quantifiers which must start with an existential quantifier $\...
- 21
0
votes
0
answers
13
views
Show that the NP vs coNP question relativises both ways
We need to show that:
there is an oracle $A$ relative to which $NP^A = coNP^A$
there is an oracle relative to which $NP^B \neq coNP^B$
While I can show the first part of this statement, I can't wrap ...
- 21
0
votes
2
answers
45
views
How to compute the complexity of $T(n) = 2T(\frac{n}{2}) +O(n\log n)$
I'm trying to solve the recurrent
$$T(n) = 2T\left(\frac{n}{2} \right) +O(n\log n)$$
I thought about Master's theorem but unfortunately, my recurrent doesn't belong to any cases
Could you please help ...
- 1
-3
votes
0
answers
35
views
Is this problem in NP. And if so why hasn't anyone used a simple problem like this to disprove P=NP [closed]
Information-
Algorithms, and you by definition cannot predict true randomness, this is a fact
2. True randomness does exist at the very foundations of matter
statement-
does P=NP. The answer is no. ...
-3
votes
0
answers
22
views
help me with my test [closed]
Select the correct output of the below algorithm with the following input:
3, -1, 2, 9, 36, -7, 6, 4
Algorithm
Input: a_1, a_2,..., a_n, a sequence of numbers
n, the length of the sequence
i, a number
...
- 1
-2
votes
0
answers
24
views
why doesn't 2SAT proof work on 3SAT
the title is quite literally my question ; why doesn't the 2sat formula work on the 3sat. I am kind of a dunce btw
0
votes
3
answers
371
views
Does the use of True randomness work in this proof for P does not equal NP
To understand this proof you must first understand
NP vs P problem
The quantum eraser experiment
True randomness
Before we start I must first assert things that have been proven to be true, if you ...
1
vote
1
answer
20
views
How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?
$\mathsf{RP}$ can be deterministically defined as:
A language $L\in\mathsf{RP}$ iff there exists a polynomial $p$ and deterministic Turing machine $M$, such that:
$M$ runs for polynomial time $p$ on ...
- 1,429
0
votes
0
answers
33
views
Proof that DFS order is P-complete [closed]
Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm ...
0
votes
1
answer
32
views
Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.
Any subarray array[start, end] ...
- 1
0
votes
1
answer
20
views
Variant of Bounded Subset Product
Edited Version
Consider the following decision problem:
Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers each less than $n^c$ and $t$ is a target natural number,...
- 1
0
votes
1
answer
26
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,429
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
57
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
59
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,429
1
vote
0
answers
28
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
24
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
39
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
81
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
16
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
36
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
17
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 ...
- 21
0
votes
0
answers
33
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
23
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
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 ...
- 133
0
votes
0
answers
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 ...
- 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
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 ...
- 21
-4
votes
1
answer
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 ...
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
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 ...
- 923
1
vote
2
answers
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 ...
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
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 ...
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
45
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
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 ...
- 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
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 ...
- 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
47
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