# All Questions

13,036 questions
Filter by
Sorted by
Tagged with
1 vote
19 views

### What role does the lower bound play in the statement of Savitch's Theorem?

Savitch's Theorem states that $\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$ for any function $f\in \Omega (\log(n))$. I don't ...
20 views

### Given a 2-player zero-sum game, 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 ...
• 176
60 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 ...
• 253
1 vote
58 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,694
55 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
55 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
107 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 ...
122 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 ...
81 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 ...
40 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 ...
67 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 ...
27 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 ...
68 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
114 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
41 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 ...
124 views
+200

### 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,694
37 views

### How to reason on composition of predicates?

Context I am working on gamma, a library to provide generics to Scheme programming language. The abstract says: gamma $\gamma$: Procedure dispatch based on predicates Create a polymorphic procedure. ...
• 121
1 vote
76 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 ...
• 11
131 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 ...
64 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 ...
66 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$ ...
1 vote
94 views

• 91
44 views

### Can an m * n matrix be given Young Tableau property in O(1) space?

If it can be done with heaps why not Young Tableaux? [1] I know that the analogy is too simplistic but for learning sake, let us consider it. The only limitation I noticed is that while heaps exhibit ...
128 views

### Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd cycle in $\mathsf{NC}$?

Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd weight cycle in $\mathsf{NC}$? I think the decision version is in $\mathsf{NC}$, but I am not sure about the search ...
341 views

### How to develop mathematical maturity required for TCS research as a computer science major?

I have been involved in mentored research with a professor whose interests lie around randomness in computation. I was lost pretty much the entire time. I was reading material at the graduate level ...
49 views

### Open source implementations of euclidean geometery automated theorem provers

I plan to work on extending a theorem prover which is specialised in generating proofs for questions based in euclidean geometry which is taught to high school students to introduce them to the ideas ...