All Questions

6
votes
3answers
2k views

Cubic graphs and hamiltonian paths

I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you
0
votes
0answers
17 views

Bi-criteria combinatorial approximation algorithms for min k-vertex cover

Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized. It is easy to ...
1
vote
1answer
52 views

Name for a special family of languages?

I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$: $\mathcal{F}$ consists ...
0
votes
1answer
30 views

Why are all finite languages regular? [on hold]

It is said that "All finite languages are regular". But the Pumping Lemma says that, if a language is regular one can find a 'large-enough' word w such that it can be decomposed into w = xyz such ...
63
votes
7answers
3k views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD). Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
0
votes
0answers
15 views

Is P-complete self-reducible?

By Self-reducibility, we understand that a search problem can be reduced to the self problem but by a decision problem instead of a function problem. P is trivially self-reducible, but what about P-...
0
votes
0answers
6 views

No cyclical variable references within a for-loop = enough?

Suppose you had a machine programming language which has: Integer variables in some field $\Bbb{Z}_n$, though for small magnitude integers, this behaves completely like we're "in the integers". ...
-1
votes
0answers
80 views

Could we use transcendental numbers as an RNG?

Numbers like pi and other transcendentals seem to have some nice properties, viz, we can't find patterns in them. Seems to me this could make them a nice candidate for RNGs, especially given that we ...
5
votes
1answer
89 views

Is F<: with bottom undecidable?

We all know that F<: is undecidable: http://www.cse.chalmers.se/~abela/lehre/SS07/Typen/pierce93bounded.pdf However, I have difficulties finding that anyone claiming the version with bottom added ...
0
votes
1answer
63 views

Lower bound of real valued bounded function

Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also Agnostic PAC sampling lower bound ) I am looking for ...
3
votes
0answers
55 views

What are CS blogs for puzzles/games?

I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?,...
-1
votes
0answers
43 views

On derandomizing $BPP$ problem

It is believed derandomizing $BPP$ to $P$ involves good PRGs and faces lower bound barriers. Does derandomizing to $P^{NP}$ face similar issue or is there evidence that it is vastly easier?
-1
votes
0answers
23 views

Counting class for DP problems

What would be the corresponding counting complexity class for decision problems in $DP$? Recall that $DP:=\{\mathcal{L}_1\cap\mathcal{L}_2\mid \mathcal{L}_1\in\text{NP},\mathcal{L}_2\in\text{coNP}\}$ (...
0
votes
1answer
52 views

About learning a single Gaussian in total-variation distance

I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown! Let $G$ ...
-2
votes
0answers
26 views

The maximum-weight subgraph problem, NP-hard? approximation?

Input: a graph $G=(V,E)$ and a weight $w_{ij}$ (possibly negative) for each edge $i,j\in V$. For each vertices $i$, there is an edge to itself, i.e., $w_{ii}$ may not be zero. Output: find a subset $...
5
votes
3answers
237 views

Probability for an element to appear in at least one set

Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct. What is the ...
-1
votes
0answers
16 views

Is this a correct way to prove the inapproximability of general k-center?

Claim: for any polynomial time computable function $\rho (n)$, the k-Center problem cannot be approximated within a factor of $\rho (n)$, unless $P=NP$. k-CenterDecision Problem: given a complete ...
-1
votes
0answers
16 views

Finding all spanning trees of a directed graph

I wonder if there is a well-known algorithm (or optimized implementation) for this.
5
votes
1answer
217 views

Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
1
vote
1answer
27 views

On-policy/Off-policy Offline/Online Evaluation: Which would be an example of Online Off-Policy Evaluation?

In the context of the following question: off-policy and offline policy reinforcement learning , it can be concluded that off-policy/on-policy learning can be orthogonal to an online/offline sampling ...
7
votes
0answers
109 views

Can relativization technique be applied to natural NP-complete languages?

Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
12
votes
3answers
844 views

Edge-partitioning cubic graphs into claws and paths

Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine. Input: a cubic graph $G=(V,E)$ Question: is there a partition of $E$ into $E_1, E_2, \...
-1
votes
0answers
30 views

Nondominated Sorting Tradeoff Curves [on hold]

Let vector a = (0, 0, 0), b = (1, 1, 1), c = (-2, 0, 3). Each index in the vector represents an objective. We wish to minimize the objectives. By this we get: Vector a dominates b because every ...
6
votes
1answer
147 views

Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
1
vote
0answers
19 views

Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that $G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$. $G$ has no left recursion; that is, we can't ...
0
votes
1answer
540 views

What does “number of inputs to each neuron” mean in Neural Network terms? [on hold]

I am reading about a Neural Networks project that has some data like this I am new to this, and though I think I understand what a 3:1 network mean, I do not understand what number of inputs (to each ...
-2
votes
0answers
22 views

Complexity of a Subset Sum variant with target dependent on elements

I would like to know whether the following problem is NP complete: For a set $S = \{(a_1,b_1,\delta_1),\ldots,(a_n,b_n,\delta_n)\}, a_i,b_i,\delta_i \in \mathbb{N}$. Does $\exists ~S^{'} \subseteq S$ ...
3
votes
1answer
100 views

Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see ...
3
votes
0answers
62 views

Is monotone 1-in-3 MAXSAT known to be APX hard?

Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause ...
3
votes
1answer
75 views

Is there a simple algorithm for proof search on CoC?

Given the usual Calculus of Constructions with an extra primitive, _, that stands for "attempt to fill this location in a way that type-checks", is there any simple/...
-1
votes
0answers
23 views

Encoding naturals in the calculus of constructions and in a language like Idris

I'm learning some type theory and trying to relate that to what I already know about proving things in Idris and similar languages. So, if I were to encode natural numbers in CoC, I'd probably have ...
9
votes
1answer
202 views

What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based ...
-1
votes
0answers
50 views

Is there any approximation factor for this algorithm?

I have a very specific question which has baffled me for a while. Assume we are given a set of pairs of integers, $T = \{(x_1,y_1),...,(x_N,y_N)\}$. We want to find a set of $k$ groups each ...
1
vote
0answers
37 views

Sketching order statistics of a stream

Suppose we have a string stream over alphabet $[n]$. At each step, we would like to compute a sketch of the last $k$ elements, such that from the sketch we can approximate their relative order. For ...
0
votes
1answer
84 views

Definitional equality of recursive function definition by “infinite unfolding”

The context is checking definitional equality in dependent type theory implementations. Consider in Coq ...
-1
votes
0answers
20 views

What makes MLT-3 better than B8ZS encoding?

In class today, my teacher explained the history of transmission of data for the internet, through cables, and how different encodings have been developed to guarantee that no clock skew occurs and ...
0
votes
0answers
28 views

Derive quantum state (bloch sphere) [closed]

I read "Quantum Computing and Information" book. On the page I found that equation (*): $$ |\psi \rangle = \alpha |0 \rangle + \beta|1 \rangle $$ can be rewritten as: (**) $$ | \psi \rangle = e^{i \...
-1
votes
1answer
2k views

Decidability of the halting problem on finite computers [closed]

I've seen two competing and contrary arguments for this problem. One states that real computers are linear-bounded automata, and therefore the halting problem is decidable. The other states that ...
0
votes
0answers
65 views

Where is the flaw in this proof that an LP solves TSP? [duplicate]

In this preprint on Arxiv, M. Diaby, M.H. Karwan, and L. Sun give a Linear Program which they claim solves the Traveling Salesman Problem. In contrast to their prior work, which was asked about here, ...
-3
votes
1answer
72 views

Are there any known languages in the intersection of NP and co-NP but not in P? [closed]

We currently don't know the relationship between NP and co-NP, but would it be possible to show whether the intersection is equal to P? I can't think of any languages in both NP and co-NP, but not in ...
2
votes
1answer
71 views

Oncina-Garcia RPNI algorithm for learning DFAs

The question refers to this paper: ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
-1
votes
1answer
106 views

Why does the Placid Platypus function grow faster than any computable function?

I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
0
votes
0answers
22 views

Computing a sum of products of ratios of QAP-like functions

Let $A \in \{0,1\}^{n \times n}$ be a binary symmetric matrix, and let $\sigma : [n] \to [n]$ denote a permutation on $[n] = \{1,\dots,n\}$. Let $S_n$ be the set of these permutations. Let us write $A^...
13
votes
2answers
622 views

Automata learning without counterexamples

In Angluin's automata learning framework, a student aims to learn a regular language $L\subseteq \Sigma^*$ by asking two types of questions to his teacher: Word queries: given $w\in \Sigma^*$, is $w\...
-4
votes
0answers
60 views

Is there any problem that cannot be solved in O(n!) time? [closed]

In other words, does a problem exist such that if we try to compute a solution it, then it's running time grows faster than n! (factorial of n)? If it does exist, give me some examples and if it doesn'...
6
votes
2answers
189 views

Is case analysis on normal forms of lambda terms sufficient to prove parametricity results?

There are many closed terms of a given type. For instance, both of these terms: $$ \lambda x . x $$ $$ \lambda x . (\lambda y . y) x $$ have a type of a polymorphic identity function: $$ \forall X ....
-1
votes
0answers
16 views

Eigenvalues of almost Laplacian matrix, particular structure

I have a square matrix of the form: \begin{pmatrix} a&b \\ -b&a \end{pmatrix} where $a = \begin{pmatrix} D1&t&0&0&t&0 ... \\ t&D2&t&0&0&t... \\ 0&...
1
vote
1answer
69 views

Computational hardness for sampling a uniform matching

A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one ...
7
votes
1answer
146 views

P and Descriptive Complexity

In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$. However, ...
7
votes
2answers
518 views

Weakly normalizing + confluent = strongly normalizing?

I was reading this abstract and saw that they prove weak normalization and confluence. My limited understanding suggests that those two properties should provide strong normalization, which then ...

15 30 50 per page