# All Questions

10,209 questions
Filter by
Sorted by
Tagged with
2 views

### How to prove a convex set is nonempty or empty in polynomial time?

I know ellipsoid method and interior method, but I do not find specific theorems to explain my question. I think that is a simplier question than optimizing an objective over a convex set. Can I use ...
137 views

### About a pre-processing step for primal–dual weighted set cover problem

I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1. They present a dual fitting based algorithm ...
219 views

### Winning strategy in the game of triplets

The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements. Two players take turns picking elements from $X$ until all elements are ...
78 views

131 views

### Type-theoretic interpretation of Skolemization

What is the type-theoretic interpretation / equivalent of Skolemization? Skolemization converts some formula into Skolem normal form. The two formulae are equisatisfiable with each other. Or, to say ...
71 views

### Characterizing the ANF of Single-Cycle Boolean Permutations

Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We ...
26 views

### An efficient algorithm for maximizing gain by choosing from a set of options

(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not ) I've got an optimization problem where I need to choose from one of several options to ...
98 views

### Model of Coq (pCuIC) in higher toposes?

Can the type theory of Coq (pCuIC) be modeled in all higher Grothendieck toposes? First of all, even the set theoretical model is not complete (e.g. inductive types in Prop). Although, this is ...
98 views

### Hospital Resident Matching Algorithm with Incomplete Preferences

Consider a set of doctors $D$ and hospitals $H$ such that each doctor $d \in D$ has a rank ordered strict preference over a subset of hospitals, $H_d \subseteq H$. Similarly, each hospital $h \in H$ ...
66 views

184 views

### Does small circuits for a NP-complete problem contradict ETH?

The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
115 views

### The Art of Computer Programming by Knuth [closed]

I recently got a Safari Books Online subscription and was excited to discover that it included The Art of Computer Programming. I've never been able to afford the paperback version, but now I have it ...
140 views

### Possibility of hierarchy with $UP$ class?

I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
128 views

### A game on several graphs

Consider the following game on a directed weighted graph $G$ with a chip at some vertex. All vertices of $G$ are marked by A or B. There are two players Alice and Bob. The goal of Alice (Bob) is to ...
299 views

### Consequences of OWFs for Complexity

It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
53 views

### Are there digraphs such that any two arborescences are arc-disjoint?

Let $D=(V,A)$ be a directed graph with root $r$. An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$. Hence an $r$-arborescence is ...
48 views

### Which algorithms can be used to measure similarity for two very different languages?

recently I have read this paper, A Survey of text similarity approaches, and I discovered that there are a lot of algorithms that can be used to measure similarity. At present I am applying the ...
49 views

### what does NP ⊆ DTIME(…) mean?

Recently I've seen inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it? Also, the paper shows that the misinformation containment problem cannot ...
58 views

### Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree

I have encountered an interesting problem that I couldn't find any references to solve: Determine the smallest subset of nodes that need to be removed from an undirected graph to make it a tree. ...
32 views

### what does “approximable to within a factor” mean?

Can someone explain what this sentence itself means? For any a > 1, problem 1 (eg. ±PSC) is approximable to within a factor of 4.a-3, if problem 2 (eg. Min-M) is approximable to within a factor of a.
418 views

### What is the hardest instance for the group isomorphism problem?

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
165 views

24 views

### A special type of pair matching case

Let's suppose we have a group of N members. We need to match the entire group or any subgroup based on the following criteria: Each group member has a matching index for another group member. 2.This ...
45 views

### Equivalent formula for LTL with and without past operators

I have recently been researching LTL with and without past operators. From my understanding, both LTL and PLTL (LTL with Past) are equally expressive, however, PLTL is exponentially more succinct. I ...
28 views

### LL(1) grammar without null productions

Every ll(1) grammar without null productions is SLR(1).what properties of ll(1) make above statement true?