All Questions
13,057
questions
-4
votes
0
answers
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 ...
5
votes
1
answer
391
views
Is there a problem known to have no fastest algorithm, up to polynomials?
Is there a problem where for all correct algorithms $A$, letting $T(n)$ be the runtime of $A$, there exists $\varepsilon > 0$ and a correct algorithm $A'$ running in time $T(n)\cdot n^{-\varepsilon}...
- 2,461
3
votes
1
answer
77
views
Halting problem with minimal Turing Machine as promised input
Consider the following Turing Machine A.
Input: Turing Machine M that recognizes some language L(M)
Output:
If M is minimal (i.e. its length is minimum among Turing Machines that recognize the same ...
- 39
4
votes
1
answer
33
views
Equal appearance of positive and negative literals in 1-IN-3SAT per variable: Is it NP-complete?
The variant is the regular 1-in-3SAT problem with only the formulae where each variable and its negation appear the same number of times in the formula.
For example, $(a\vee b\vee\neg a)\wedge(\neg a\...
- 41
0
votes
0
answers
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....
0
votes
0
answers
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 ...
- 1
-1
votes
1
answer
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
-3
votes
0
answers
24
views
NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) reduction to NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) always exists?
Does reduction between NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) to NOT(𝑅𝐸∪𝑐𝑜−𝑅𝐸) always exists?
4
votes
1
answer
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 ...
- 141
1
vote
1
answer
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:
...
- 11
0
votes
1
answer
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 ...
-1
votes
1
answer
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) ...
-4
votes
0
answers
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.
- 1
2
votes
0
answers
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
0
votes
0
answers
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}.
...
- 1
0
votes
0
answers
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
4
votes
0
answers
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?
3
votes
1
answer
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
3
votes
0
answers
100
views
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
It is easy to show that the relaxed version ($\mathsf{E} \subset \mathsf{NP}$ and $\mathsf{P}^{\mathsf{NP}} \...
- 271
1
vote
0
answers
37
views
Can a combinator basis set of size two have an arbitrary combinator?
The S and K combinators are a known basis set of combinators. Such a set is called universal. However, two combinators being universal is the limit on universality, as a single combinator cannot be ...
- 11
-2
votes
0
answers
69
views
Can PA model a Turing machine verifying a proof in ZFC that PA is consistent?
I've made the following assumptions:
In the language of ZFC, there is a proof that PA is consistent.
You can construct a Turing machine which verifies proofs written in ZFC.
Peano Arithmetic can ...
- 215
4
votes
0
answers
144
views
Minimum Regular Expression for Strings not Containing Substring?
Given an alphabet $\Sigma$ and a fixed nonempty string $w$, consider the problem of finding a minimum regular expression $R(\Sigma, w)$ for all strings in $\Sigma^\star$ that do not contain $w$ as a ...
- 613
0
votes
0
answers
34
views
Are there approaches to deriving a Grammar(production rules) from given set of strings?
Apologies for unambiguous question. So far I have a lot of difficulties of discerning on how to design formal production rules for some formal language aside from classic examples such as equal pairs ...
- 9
3
votes
2
answers
166
views
Admissible rules in dependent type theory
From the nlab article on Martin-Löf dependent type theory:
The weakening and substitution rules are admissible rules: they do not need to be explicitly included in the type theory as they could be ...
- 31
0
votes
0
answers
64
views
Incremental path (graph theory)
I have the following problem, which I don't know how to solve. Can anyone help me? Algorithm needs to be in $O(n^2 log\ n)$
Input:
A matrix $C[1..n][1..n]$ with the costs of the edges $\{i,j\}$, where ...
- 1
2
votes
0
answers
78
views
Implication of having a classical oracle separation for $QMA$ and $QCMA$
There is a known quantum oracle relative to which QMA is not contained in the QCMA class. [Aaronson & kuperberg '07]
It is unknown if there exists a classical (deterministic) oracle relative to ...
- 295
-2
votes
1
answer
97
views
How to find regular expression using ardent's rule for recursive expressions? [closed]
I have the following automata:
States = {A,B}
Transitions = { (A,0,A), (B,0,B), (A,1,B), (B,1,A) }
Initial state = A
Final state = B
Inputs = {0,1}
Here if I try ...
- 5
5
votes
0
answers
200
views
How to prove following weighted forest problem is NP-hard?
I am studying the following weighted forest problem, which is an optimization problem in graph theory focused on finding optimal forest structures in robust scenarios. The problem is defined as ...
- 51
1
vote
1
answer
73
views
Norm in the definition of sampling computational complexity class SampP
This paper defines the class of sampling problems SampP (see Definition 11). It requires that the probability of the generated samples $C_x$ is close to the target probability $D_x$ within an error $\...
2
votes
0
answers
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
3
votes
1
answer
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 ...
- 33
5
votes
0
answers
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
2
votes
0
answers
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
0
answers
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
0
votes
0
answers
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
0
answers
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
5
votes
0
answers
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 ...
5
votes
2
answers
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 ...
- 53
6
votes
0
answers
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 ...
- 161
-2
votes
0
answers
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 ...
0
votes
0
answers
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
0
answers
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 ...
- 11
2
votes
0
answers
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 ...
- 567
1
vote
1
answer
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
0
answers
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 ...
- 11
7
votes
0
answers
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
2
votes
0
answers
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
4
votes
0
answers
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 ...
- 41
2
votes
0
answers
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 ...
2
votes
1
answer
70
views
Complexity of a variation of edge cover for paths
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$ ...
- 21