Questions related to the (computational) complexity of solving problems
0
votes
1answer
5 views
Regarding time complexity of multi-tape Turing machines
So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM?
I just don't know where to get started...
1
vote
1answer
24 views
Deleting edges such that largest connected component has at most $n/4$ nodes
Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges.
Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific ...
1
vote
1answer
39 views
provably optimal search algorithms?
In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-...
1
vote
1answer
27 views
A relationship between Kolmogorov complexity and prime divisors
Given a positive strictly monotonically increasing infinite sequence $n_1, n_2, \dots$ with Kolmogorov complexity
$$K(n_i)\geq\lceil\log_2 n_i\rceil/2\,.$$
If $q_i$ is the greatest prime number that ...
0
votes
0answers
21 views
Minimal hashing function for integers that satisfy specific constraints
I'm looking for a kind of way to create a minimal perfect hash function given a set known integers.
More specifically, I have M numbers within the range 0-N with N > M.
Does it exist a way to create ...
0
votes
0answers
21 views
Find asymptotic bounds $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$
Give the recurrence relation:
$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$
($k$ is some constant and assume $n$ is $2^t$ for some $t\in \mathbb{Z}$)
I'm trying to ...
1
vote
1answer
18 views
reducing a decision problem to a local search problem
Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states:
If a PLS problem is NP-hard then NP = P
So assuming L is a PLS problem (polynomial local search problem) that ...
0
votes
1answer
24 views
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).
I know that ...
2
votes
0answers
33 views
Card dealing problem with constraints (blacklisting),
A friend of mine and I are trying to teach a bot play a card game (bela)
We are using monte carlo tree search (MCTS) to estimate the probability of winning hand in regards to multiple possible (!...
0
votes
0answers
17 views
Quick search of objects based on distances
I have some objects $x\in X$ and a metric $s:X\times X\to\mathbb{R_{+}}$. For each $x$, there is a $y\in Y$. Note that $x$ and $y$ are highly structured and we cannot consider neural networks for ...
-2
votes
0answers
20 views
CYK vs Earley algorithm [on hold]
What are the differences between CYK and Earley algorithms? Please provide a thorough rundown.
1
vote
1answer
9 views
Alternative formulation of complexity class $BPP$
In Aurora and Barak, they give the following alternative definition of $BPP$:
What is the meaning of the subscript to $Pr$? Is that $Pr_{r \in_R \{0,1\}^{p(|x|)}}$? My guess is this is supposed to ...
1
vote
0answers
11 views
Other problems in UP and co-UP
Are there any known problems in $UP \cap co-UP$ other than integer factorization and parity games (or a problem that can be reduced in polynomial time to either problem), that aren't known to be in $P$...
0
votes
0answers
24 views
If you have two recursive calls in a function and one terminates before the second how do you calculate the time complexity? [duplicate]
Suppose you have a function which calls to itself twice. So both go down recusively until they reach some condition. But one of them will go less times than the other. For example one would call ...
0
votes
1answer
11 views
Can any problem that runs in exponential time on a deterministic RAM be run in polynomial time on a non-deterministic RAM?
If P is a program that can be run in exponential time on a deterministic RAM. Can P always be run in polynomial time on a non-deterministic RAM?
1
vote
0answers
13 views
How to check a graph diameter in LOGSPACE?
Given a graph G, how can I check that its diameter doesn't exceed log(n) (n is the number of vertices)- by using only O(log(n)) space? (adjacency matrix doesn't seems to help...)
0
votes
1answer
52 views
2SAT Problem using Implication Graph
I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each ...
0
votes
0answers
24 views
Scheduling with minimum staffing requirements and preferences
I'm interested in the following scheduling problem:
Time is divided in $T$ slots as represented by the left circle below (where $T = 8$). A minimum number of employees $b_t \geq 0$ need to be present ...
3
votes
1answer
34 views
Why is dominating set in $W[2]$, but independent set in $W[1]$
In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape ...
0
votes
0answers
16 views
Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits
I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is ...
0
votes
1answer
71 views
Algorithms for elementary operations using other elementary operators
The question asks to provide an algorithm to compute
$(i)$ The product of $n$-bit numbers using
reciprocation operation and addition operation but not using multiplication
and squaring.
$(ii)$ The ...
0
votes
0answers
23 views
Is the following language regarding P=NP/P!=NP decidable? [duplicate]
Let A = {w|w $\in$ {0,1}, such that
w=0 iff P=NP
w=1 iff P!=NP
Would the language itself be decidable?
-1
votes
0answers
14 views
Collect stamps, algorithm
Suppose you have a box full of stamps. There are $a$ stamps in the box. You want to get the $b$ oldest stamps from the box. Whereby $a$ is much bigger than $b$. What would be the best algorithm (worst-...
1
vote
0answers
19 views
Complexity of bisection method for finding an interval
Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]...
0
votes
1answer
71 views
How can I show that a problem is not $NP$
Consider the following image:
The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$.
I ...
0
votes
0answers
27 views
Checking if the clauses are satisfiable
I want to test if this clause: {x,y,z},{¬x,y},{¬y},{¬z} is satisfiable.
However, I noticed that the clauses contain more than two literals. How can I check whether the formula is satisfiable.
So ...
0
votes
0answers
35 views
Using Implication Graph to check 2-Satisfiability
I have the following boolean formula: {x,y},{-x,-y},{x,-y}, and below is the corresponding Implication graph:
I know that the next step is to check for 'bad loops'/Strongly Connected Components. ...
0
votes
0answers
18 views
Understanding the logic of algorithm runtime
I'm trying to understand the runtime of this code:
def f(n):
if (n <= 1):
return 1
else return f(n-1)*f(n-1) + f(n-1)
At first, my logic said ...
6
votes
1answer
106 views
Does finding a cycle with $\log n$ length in $\text{P}$?
Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?
0
votes
0answers
22 views
How to prove that this TSP variation is NP-Hard?
The problem is as follows: given a list of cities, a list of distances between them, and upper bounds for date/times that the cities must have been visited by, compute the shortest (optimal) going ...
1
vote
0answers
18 views
Complexity class without fixed-poly size circuit
$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.
Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.
In notation, ...
1
vote
2answers
50 views
What is the real reason that Bubble Sort runs at O(n) in best case?
In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only ...
1
vote
2answers
68 views
If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?
I came across this question while studying for an exam:
T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ ...
1
vote
1answer
23 views
Complexity of two cycles which differ by $1$ in length
Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length.
What is the complexity of this problem?
2
votes
1answer
57 views
Is SAT known to be non-context-free or even non-regular?
We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.
Has something similar been done for SAT?
1
vote
1answer
16 views
Relation beetween log-space reduction and polynomial time reduction
I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
0
votes
0answers
20 views
All the ways in which Turing machines are used
The Turing machine model can be used to do computation in several ways. Two ways I know are:
For a Turing Machine that checks whether a particular string is present in a language or not, when the ...
1
vote
1answer
12 views
Circuits vs Turing Machines in the “nonuniform model of computation”
I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the ...
0
votes
0answers
19 views
$\mathbb{NEXP\subseteq(NEXP\cap coNEXP)/poly}\implies \mathbb{NEXP=NEXP\cap coNEXP}$
We already know that $NEXP\subseteq EXP/poly\implies NEXP=EXP$. What if we change $EXP$ to $NEXP\cap coNEXP$.
As the title states, prove the statement in the title.
The original proof use the self-...
1
vote
1answer
23 views
complexity classes defined as limits or “globally”?
As far as I understand correctly, to say that a decision problem $X$ is in P means that there exists a polynomial $c\cdot n^p$ such that as $n$ goes to $\infty$, the steps required to solve $X$ is ...
-2
votes
3answers
76 views
The most subtle NP-“intermediate” problem
What is the $NP$ problem which status (in $P$ or $NP$-complete) is still unsettled, as of 2018?
This question is inspored by the following two recent breakthroughs:
The work of Mulzer et. al on $NP$-...
2
votes
1answer
29 views
Computational complexity of maximizing sum of rational functions
I have a optimization problem:
$$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
1
vote
1answer
22 views
Subset sum exponential solution - how does the sorting work?
The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements. You then generate all the subsets for each list (each having ...
2
votes
0answers
32 views
Theoretical performance measures other than worst case
Suppose that $P \neq NP$, and $P = BPP$.
Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
0
votes
1answer
14 views
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
-1
votes
0answers
16 views
Can we assume that a UTM is equivalent to a programming language? [duplicate]
I wanna know can we assume that a Universal Turing Machine is equivalent to a programming language like C++?
The main question is can the gcc compiler work as a UTM or not?
I know we can implement UTM ...
-1
votes
2answers
73 views
Reduce EXACT 3-SET COVER to a Crossword Puzzle
I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point and if anyone ...
2
votes
1answer
46 views
Is there an asymptotically optimal algorithm for unbounded search?
Suppose you have files with size $1,2,3,4\dots$ (which can be arbitrarily large and which have and can have any value that you want) and a USB-stick whose memory size $s$ you don't know, where $s$ is ...
0
votes
0answers
20 views
Sieve of Eratosthenes, time and space Copmplexity
The Sieve of Eratosthenesis an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list.
what is the time and ...
0
votes
0answers
17 views
Implication of Mahaney's Theorem
Not having received an answer to this question on Math.SE, I am asking it here.
According to this source, Mahaney’s Theorem states that:
An $NP$-complete language $L$ is Karp-reducible to a sparse ...
