Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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$ ...
adelta's user avatar
  • 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 ...
rus9384's user avatar
  • 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 (...
Dannyu NDos's user avatar
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 ...
user1868607's user avatar
  • 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 ...
circuitman324's user avatar
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 ...
rus9384's user avatar
  • 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 ...
Yury's user avatar
  • 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\}^*$ ...
KJL's user avatar
  • 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 ...
asamsa's user avatar
  • 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....
ltl's user avatar
  • 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 ...
Maceo Cardinale Kwik's user avatar
-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.
Anthony Shuey's user avatar
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 ...
Meki21's user avatar
  • 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 ...
Oluchi A's user avatar
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?
Philipp's user avatar
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 ...
River Uzoma's user avatar
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}...
wsz_fantasy's user avatar
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 ...
Sriram's user avatar
  • 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 ...
someone's user avatar
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 ...
Dennis Gahm's user avatar
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 ...
Meki21's user avatar
  • 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 ...
Anthony Shuey's user avatar
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 ...
Santiago Armstrong's user avatar
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 ...
SmallestUncomputableNumber's user avatar
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 ...
Alex Meiburg's user avatar
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 ...
Aditya Mishra's user avatar
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?
NotaChoice's user avatar
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 ...
Placido Pellegriti's user avatar
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 ...
mathbreaker's user avatar
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 ...
Kagura Hitoha's user avatar
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 ...
Tung Nguyen's user avatar
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 ...
void's user avatar
  • 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 ...
void's user avatar
  • 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 ...
dsjoint's user avatar
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 ...
licheng's user avatar
  • 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 ...
Turambar's user avatar
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} \...
Nancy Drake's user avatar
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 ...
AmirD's user avatar
  • 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$...
Pipnap's user avatar
  • 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})...
calveeen's user avatar
  • 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$ ...
calveeen's user avatar
  • 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 ...
calveeen's user avatar
  • 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 (\...
ShyPerson's user avatar
  • 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 ...
Dilfira Kudrat's user avatar
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 ...
user93353's user avatar
  • 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 ...
roignoirewg's user avatar
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 ...
J.Doe's user avatar
  • 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 ...
LargeHorse's user avatar
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 ...
quTANum's user avatar
  • 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 ...
gangsterio's user avatar

1
2 3 4 5
107