# All Questions

10,594 questions
Filter by
Sorted by
Tagged with
89 views

### Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover. Let $G$ be connected simple graph. $k$-clique cover of graph $G$ is partition ...
63 views

### Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

(This question is inteneded for people who have heard of "Vertex Partitioning Problems" framework of Telle and Proskurowski. Others may dig in only if they are interested in practical algorithms for ...
91 views

### Is the counting version of 1-in-3 Sat #P-complete?

In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat. Cubic Planar Positive 1-in-...
122 views

### Known property? Maximum radius of connected induced subgraph

I was wondering if the following graph property has a name and has been researched: Consider any connected induced subgraph $H \subseteq G$. Then $r(G)$ denotes the maximum radius of any such $H$. I ...
86 views

### Determining if a word of specific length exists that is not accepted by a NFA

It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard? Given an NFA and a ...
46 views

### Randomized Reduction for Maximization Problem

I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
83 views

### NP-Hard Knapsack Instances

Consider the classic Knapsack optimization problem (KP): Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ ...
1k views

### Is there a result in computability theory that does not relativize?

I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that Our axiomatization has its limit: it cannot prove any results in computability ...
92 views

### Is this a good definition of computability? [closed]

I still haven't found a good definition of computability. All the definitions are either too vague, or they delegate the definition to another loaded term like "anything that uses math to solve a ...
184 views

### Fast algorithms for evaluating functions with high Kolmogorov complexity

Motivation: I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I ...
100 views

89 views

190 views

### Latest word on cross validation?

It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with ...
545 views

### Examples of the value of proofs for algorithms

In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US ...
150 views

### A Simple Auction Game

You are playing the following game. You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a ...
206 views

### Applications of Barendregt–Geuvers–Klop conjecture

I was learning about type systems from Benjamin C. Pierce's Types and Programming Languages and came across the Lambda cube in the chapter on Higher-Order Polymorphism. After reading up more about it ...
88 views

### Isomorphic subforest problem

I recently read that the following problem is NP-Complete: Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$? The reference provide was to the textbook “Computers and ...
437 views

### Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP. Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper. Some Examples: 1. A paper by Shuichi ...
30 views

### What is the current state of the art with respect to First Order Bayesian Networks?

The below is a survey paper: https://ieeexplore.ieee.org/document/5579472 Is there any significant updates to this? They mention Bayesian Logic Programs (BLP), Bayesian Logic (BLOG) and Multi-Entity ...
82 views

### In quantum money schemes, how is the list of serial numbers provided?

Public key quantum currency generally includes $k$ pairs ($S_\psi,\vert \psi\rangle)$ of classical information (bits) $S_\psi$ and quantum information (qubits) $\vert \psi\rangle$. In many examples,...
122 views

### Understanding non-equivalence of proof lengths according to proof systems

Here, in section 4.3, Fortnow says: But to prove P != NP we would need to show that tautologies cannot have short proofs in an arbitrary proof system. I am ...
1k views

### Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier. For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine ...
207 views

### Prime factorisation of decidable problems

Disclaimer: I am not a theoretical computer scientist. The set of decidable problems $\mathbb{D}$ is countable so $\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$ and this led me to the ...
50 views

Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \... 2answers 1k views ### NP-hard problems with very fast exponential-time algorithms NP-hard problems with very fast exact exponential-time algorithms, say with$O(1.01^n)$time, are very rare. Is any fact like "For any constant$\epsilon>0$there is an NP-hard 'natural' ... 0answers 56 views ### Complexity of multi-objective optimization problems How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)? It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ... 1answer 803 views ### Knapsack with dependent profits (pairs of items) I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items$e_i$and$e_j$have profit$p_i$and$p_j$respectively. However, if both items are present in ... 2answers 251 views ### Maximum shortest word accepted by pushdown automata Given a fixed alphabet, consider all deterministic pushdown automata with$n$states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ... 1answer 86 views ### Meet of integer partitions An integer partition of$n$,$A$, is a multiset of positive integers such that$\sum_{a \in A} a= n$. We say that$B \leq A$, if there exists a map$\phi: |B| \to |A|$, such that for$a \in A$, we ... 1answer 71 views ### About estimating escape time of gradient Langevin dynamics I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly ... 1answer 865 views ### Consequences of$\oplus \mathbf{P} \subseteq \mathbf{NP}$I have part of a proof attempt of$\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the$\oplus \mathbf{P}$-complete problem$\oplus\$3-REGULAR VERTEX COVER ...

15 30 50 per page