All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
2
votes
1answer
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 ...
7
votes
1answer
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 ...
3
votes
1answer
78 views

Complexity of #PP2DNF where we also count on the number of clauses

The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \...
1
vote
1answer
70 views

Consequences/existence of problems without any “optimal” algorithm

Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off ...
-1
votes
0answers
26 views

Functions Associative with Respect to Application

How to construct λ-terms, which are associative with respect to application? E.g., how to construct f and g, such that for any x: f (g x) = (f g) x (i.e. f g x) How to construct some closed set ...
6
votes
1answer
131 views

3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
0
votes
0answers
30 views

Knapsack Variant

I’m looking for algorithms to solve the following Knapsack variant: Given: A Knapsack of fixed size; A set of K item types. Item size within each type may be chosen/selected/solved-for between two ...
0
votes
2answers
338 views

Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
10
votes
2answers
446 views

Lattice problems

There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...). I am curious what work specific to ...
2
votes
1answer
152 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 ...
-4
votes
0answers
38 views

How to prove of disprove the following Control Flow Graph theory

See the attached image for some background on Control Flow Graph In a single-entry, single-exit control flow graph (CFG), a node u post-lead v if every path from v to the exit includes 𝑢. Let q be ...
13
votes
5answers
429 views

When have we found better bounds for known algorithms?

Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - ...
0
votes
1answer
463 views

What kind of reinforcement learning is MENACE?

The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description: ...an interesting machine ...
1
vote
0answers
39 views

State of the art Luby Transform code usable in Raptor codes?

I've just read Raptor Codes by Amin Shokrohalli which introduces linear-time fountain codes that needs $(1 + \varepsilon)k$ output symbols to recover the $k$ input symbols with high probability. A ...
5
votes
0answers
148 views

Nondeterminstic Linear Time vs Other Complexity Classes

Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
7
votes
1answer
237 views

Can reciprocal inputs speed up monotone computations?

A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
6
votes
1answer
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 ...
4
votes
0answers
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 ...
-2
votes
0answers
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 ...
8
votes
0answers
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 ...
-1
votes
2answers
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$ ...
4
votes
1answer
66 views

Complexity of Parallelogram Range Minimum Query

Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs? More formally, answering the query $$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$...
3
votes
1answer
81 views

Deterministic Realtime Languages

Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) prove that non-deterministic linear time ...
1
vote
1answer
48 views

Correlation between noise resilience and output distribution of Boolean circuits

Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at ...
8
votes
1answer
429 views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...
-2
votes
0answers
66 views

Is BQP upper bounded by the class of problems computable by an exponential number of GPUs?

Consider the class $EXPGPU$ that informally contains all problems that can be stocastically solved in polynomial time by an exponential number of processors. Question: Is $BQP \subset EXPGPU$? My ...
4
votes
2answers
276 views

A variant of #POSITIVE-2-DNF

Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations ...
3
votes
0answers
87 views

Earliest forbidden subgraph characterisation

I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ? Of course, bipartite graph is one example but I am considering it as trivial ...
5
votes
1answer
189 views

The asymptotic behavior of a recurrence related to stable matchings

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows: $$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$ Apparently, Knuth was able to prove that ...
12
votes
0answers
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)}$ ...
-2
votes
0answers
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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 ...
9
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
-4
votes
1answer
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 ...
2
votes
0answers
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. ...
-3
votes
0answers
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.
10
votes
1answer
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, ...
0
votes
0answers
165 views

On PP in communication complexity

Aho says $D(f)=O(N(f)N(\overline f))$ where $D(f)$ is deterministic communication complexity and $N(f)$ is non-deterministic version. Do we know $PP(f)=\Omega(2^{(N(f)N(\overline f))^{O(1)}})$ or $...
3
votes
1answer
80 views

Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
3
votes
0answers
220 views

Difficulty of graph coloring and independent set?

Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable. Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
0
votes
0answers
41 views

Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
-1
votes
0answers
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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?
-2
votes
0answers
60 views

Comparisons between Graph isomorphism algorithms

I have heard quite a few algorithms for isomorphism tests. Can anyone tell me which one is the best and their difference? More specifically, what is the relationship between Weisfeiler-Lehman and VF2 ...
-1
votes
0answers
70 views

Any worked examples of Block Sensitivity?

So this proof of the Sensitivity Conjecture is making interesting waves (ie. the conjecture is sufficiently interesting, and the proof is sufficiently small (Donald Knuth has it down to one page now......

15 30 50 per page