# All Questions

13,057 questions
Filter by
Sorted by
Tagged with
46 views

### Is this a sufficient condition to prove P is not equal to NP?

I suppose {1} refers to the following problem, which I will call B. Instance: A binary string b Question: Is b=1? It seems, P=NP would imply B is NP-hard via polynomial-time reductions. Indeed, assume ...
391 views

• 41
26 views

### Two-stage Robust Shortest Path Problem - worst- case second-stage of an optimal solution

in the paper Improved Approximations for Two-stage Min-Cut and Shortest Path Problems under Uncertainty chapter 4, they are using an algorithm to approximate the two-stage robust shortest path problem....
46 views

### Why can negating '$\Phi(G) \geq \Omega(\phi)$' be converted to '$\Phi(G) <3\phi$' in this proof instead of '$\Phi(G) < c \cdot \phi$ for all $c > 0$'?

If we want to negate the statement '$\Phi(G)$ is at least $\Omega(\phi)$', the result is usually '$\Phi(G) < c \cdot \phi$ for all $c > 0$'. However, I found that a contrapositive only indicates ...
92 views

### Is any procedure satisified by the principle of least action able to be simulated by Turing Machine?

The Hamilton action $S$ is defined as following: $$S=\int^T_0 L(q,\dot{q})dt$$ the integral along any actual or virtual (conceivable or trial) space-time trajectory q(t) connects two specified space-...
• 1,077
24 views

### NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) reduction to NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) always exists?

Does reduction between NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) to NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) always exists?
130 views

### A potentially novel complexity measure for sets of strings

Inspired partly by Scott Aaronson's post about the first law of complexodynamics, I've been thinking lately about how to quantify the "interesting" or "structured" complexity of a ...
1 vote
64 views
+100

### Can a Queue with Fewer Serves outperform a Queue with More Servers?

I am working on simulating an MMK queue with the following parameters: ...
74 views

### Finite sets in Coq

I am a beginner and trying to figure out how to work with finite sets and maps in Coq. I want to define an inductive type X with a single constructor that takes as an argument a finite set of elements ...
60 views

### Computing non-halting inputs of semantic non-equivalent programs

Let P and Q be two programs take one natural number as input and produce no output and they are not semantically equivalent, that is, there exists at least one input value n such that either P(n) ...
31 views

### How do I iterate over (w* y*)* [closed]

0 {ε} 1 {{w, y}, {wy, ww}, {www, wwy, wyy, yyy}, …} W can’t be after an Y 2 { ? } I still cant figure out how nested stars behave.
29 views

### Is PP non-adaptively random self reducible?

It is well known that $\mathsf{\#P}$ is non-adaptively random self-reducible, with the common proof given via the permanent. Feigenbaum and Fortnow showed that this implies $\mathsf{PP}$ is adaptively ...
• 61
29 views

### Python : Regex to min-DFA - help with repetition {n,m} and {n, } [closed]

I wrote a program in python to process a regex string into DFA, so far i got all operations working (kleene star, union, alteration, nester parentheses, epsilon transition and single repetition {n}. ...
33 views

### Is the problem of maximizing the weight loss in a spanning tree with edge restoration NP-hard?

Given $G = (V, E, w)$, an undirected weighted graph, where $V$ is the set of vertices, $E$ is the set of edges, and $w: E \rightarrow \mathbb{R}^+$ is a function assigning positive real weights to the ...
• 51
113 views

### Implementation of László Babai's Graph Isomorphism Algorithm

Has anyone (that we know of) ever actually implemented László Babai's algorithm for graph isomorphism in quasipolynomial time? If not, would such a thing even be possible/feasible?
326 views

### Does ETH imply P vs NP is decidable?

I have been reading Scott Aaronson's summary paper on P vs NP. In this paper, there was a section about the likelihood of the problem being undecidable (page 28). He mentions a paper that I could no ...
• 59
100 views

141 views

### Is $K^t$ complexity closed under composition

Call a function $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ reasonable if $\forall c \in \mathbb{N}, \exists_\infty n, c K^{2n}(n) \leq \alpha (n)$. Where $K^t$ is the time bounded Kolmogorov ...
• 309
86 views

### Escaping the cycle: Route planning in graphs with conditional logic

Given a directed graph $G(V, E)$, I want to find a route, $R \in E^*$ from $S$ to $T$ for $S,T \in V$. If $G$ includes a cycle, how can I find a route that includes $n$ iterations of the cycle before ...
115 views

### Given a 2-player zero-sum game in EFG, find a pure Nash equilibrium (given that one exists)

Say we want to find a pure Nash equilibrium of a 2-player zero-sum (2P0S) game. A pure equilibrium does not exist for all games, so let's consider the setting where we are promised that such an ...
• 206
157 views

### How powerful is Quantum Turing machine with an oracle access to NP?

I would like to know the upper bound on the class of problem efficiently solved by a BQP (machine) with access to: (i) a single (oracular) call to NP machine (or, $BQP^{NP[1]}$) (ii) poly-logarithmic ...
• 295
1 vote
80 views

### Definition of unambiguity in alternating finite automata

I would need to know if somebody in the literature studied the concept of unambiguity in the context of alternating finite automata (AFA). Of course there's a lot of work on unambiguity in NFAs, and I ...
• 1,704
75 views

### Witness for NL Computation

For any NP language, we usually describe the language as having a polynomial time TM M such that for yes instance x you can find a witness such that M(x, w) accepts and for no instance M will not ...
1 vote
65 views

### Complexity of single bit recovery version of Integer Factorization problem

Consider the integer factoring problem with exactly 2 prime factors $p.q=N$. Given $N$ find the prime factors $p$ and $q$. The problem is notoriously difficult (on classical computers) and is the ...
• 831
144 views

### Is this class between BPP and PP?

In analogy to BPP, I define a class XYZ (maybe it already has a name) as follows. For every language $L$ in XYZ, there is an algorithm $M$, such that: $M$ runs in polynomial time on the size of its ...
308 views

### Orientations of an undirected graph

I would like to ask about an approach to find the min. number of edge orientations to ensure that a specific subset of nodes (between which demand exists) in a weighted undirected graph is eventually ...
103 views

### Extensions of linear integer arithmetic decidable via Deterministic Pushdown Automata

I've recently learned about the connection between linear integer arithmetic (Presburger arithmetic) and Deterministic Finite Automata (DFAs). Namely, any formula in the first order theory of ...
52 views

### Source for the "Recursion Theorem" in the context of Turing Machines

Hi and thank you for reading me, I saw a result that interests me in this lecture by Shalev Ben-David, called the "recursion theorem" (Theorem 19.1). It roughly states that : Fix an input ...
72 views

### Regatta Scheduling Problem

I think I have a Hamilton path finding problem, with a twist. No one asked me to solve this, but I'm trying to do it anyway. I'm rowing in a regatta tomorrow. There are about forty-two crews in the ...
1 vote
32 views

### PAC-learning description of (quantum) hypothesis class containing randomness

I was wondering how to correctly describe the following hypothesis class mathematically correctly: Say I have a quantum circuit which I postprocess by feeding its results into a neural network. How ...
81 views

### When is an upper bound on the longest irreducible program outputting something computable?

This is a repost of this mathoverflow question. Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program ...
1 vote
127 views

### Graph canonization vs. NP

Is graph canonization (GC) in NP? Is it NP-hard? If unknown, what would be your best guess and why? GC is GI-hard (GI-completeness is unknown), with the graph isomorphism problem being in NP and a ...
• 267
1 vote
49 views

### Streaming when doing computations with abstract term rewriting systems?

Computation models such as interaction nets can represent any computation as they are Turing complete. However, I have been investigating their practical implementations, and I'm wondering if there's ...
140 views

### Bounds on the length of simple paths in DFAs resulting from the powerset construction of an NFA

In general, a DFA $P(A)$ resulting from the powerset construction of an $m$-states NFA $A$ may have $2^m$ states, and a simple path traversing all these states is often there. However, I cannot find ...
• 1,704
137 views

### Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks

Context I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
• 21
146 views

### Any advice for a third-year undergraduate student who wanna embark on tcs research in the future?

I'm about to be a third-year undergraduate student next month. There're not too many opportunities to do theory research(there are some but I think I'm not interested) especially for those without ...
73 views

### Learning a boolean function using decision tree with small number of queries

I am working on a problem and I am looking to solve the following subproblem : Given a "restrictive" blackbox access to boolean function $\phi$, output a "small-sized" CNF that ...
Consider the following problem. Given a directed acyclic graph $G=(V,E)$ with a designated source vertex $s\in V$ and sink vertex $t\in V$, and natural number $k$. Find a smallest set $E'\subseteq E$ ...