Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0 votes
2 answers
28 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 ...
Pipnap's user avatar
  • 1
-1 votes
0 answers
23 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. ...
ChadTheVlad's user avatar
-3 votes
0 answers
21 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 ...
nawa's user avatar
  • 1
-2 votes
0 answers
22 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
ChadTheVlad's user avatar
0 votes
3 answers
358 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 ...
ChadTheVlad's user avatar
1 vote
1 answer
19 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 ...
rus9384's user avatar
  • 1,429
0 votes
0 answers
32 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 ...
Robin Petr's user avatar
0 votes
1 answer
26 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] ...
patayala's user avatar
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,...
adelta's user avatar
  • 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 ...
rus9384's user avatar
  • 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 (...
Dannyu NDos's user avatar
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 ...
user1868607's user avatar
  • 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 ...
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,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 ...
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
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 ...
asamsa's user avatar
  • 11
1 vote
1 answer
68 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
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 ...
Maceo Cardinale Kwik's user avatar
-2 votes
0 answers
33 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
15 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
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 ...
Oluchi A's user avatar
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?
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
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 ...
Sriram's user avatar
  • 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 ...
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
28 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
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 ...
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
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 ...
Alex Meiburg's user avatar
1 vote
2 answers
98 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
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 ...
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
45 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
93 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
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 ...
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
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 ...
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
27 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
37 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

1
2 3 4 5
107