All Questions

Filter by
Sorted by
Tagged with
1
vote
0answers
25 views

What is the complexity of checking equivalence of two boolean formulae without NOT symbol?

Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used. I.e. only conjunction and ...
6
votes
1answer
41 views

Complexity of finding an edge set yielding specified vertex degrees

I'm trying to figure out if the following two problems are known in general to be in P or NP-complete: Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'...
3
votes
0answers
30 views

$NP$-Completeness of $\epsilon$-balanced graph parittioning for fixed $\epsilon$

Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
-2
votes
0answers
25 views

Design a NFA and DFA which accepts: (1+01)*(0+00)(1+10)* [closed]

This is the DFA I came up with, but it does not match the answer. I can't find the mistake. Any help will be appreciated
4
votes
0answers
36 views

Relaxed minimum dominating set

(I moved this question from cs exchange to here, because it might be more on the topic here) Let $G=(V,E)$ be a directed graph with $n$ nodes. For a subset of nodes $S\subseteq V$, let $\mathcal{N}(S,...
9
votes
0answers
72 views

NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
0
votes
0answers
33 views

Formal proof of undecidability that a TM will halt if a subfunction inside it halts [closed]

How do I formally prove that a TM/algorithm that contains a condition checking if another program halts is undecidable? Consider function FUNC(i) ...
-2
votes
0answers
32 views

Semantic property and Non-trivial Turing Machine [closed]

I have some TM M. My question is: Is it decidable that such M exists? Is thsi a non-trival semantic question about a property of TM?
7
votes
0answers
103 views

Algebraic methods for testing planarity

Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
-2
votes
0answers
37 views

What does “use TM $M$ subroutine” really mean? [closed]

I have seen some proofs in reducibility for proving decidability and undecidability that always talks about "using TM as a subroutine". Usually, this is to prove that something that uses a subroutine ...
3
votes
0answers
88 views

Terminology: FNP, with P replaced by NP?

Consider these two classes of search problems: Search problems with poly-sized solutions s.t. verifying solutions is in P. Search problems with poly-sized solutions s.t. verifying solutions is in NP. ...
-1
votes
0answers
46 views

How to prove that $a^nb^{2^n}$ context-sensitive language? [closed]

What I know: This language is not CFL because of pumping lemma. But we could create a Turing machine (an algorithm) that recognizes this language. Is this language Context-Sensitive Language? How do ...
4
votes
1answer
124 views

What are the criteria for inviting conference papers (e.g. SODA) for special issue?

This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA ...
2
votes
0answers
73 views

Matrix multiplication when one matrix is fixed

Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry One is allowed to pre-process this matrix as appropriate. Given another positive integer entried $B$...
-2
votes
0answers
50 views

$BPP$ type algorithms with slightly more capability

A language $L$ is in $BPP$ if and only if there exists a polynomial $p$ and deterministic Turing machine $M$, such that $M$ runs for polynomial time on all inputs For all $x$ in $L$, the fraction of ...
-4
votes
0answers
44 views

Problem related to Completeness : P = PC [closed]

I am learning computational complexity. So, i took some practise problems from internet. I came across 1 problem which I am not sure whether my solution is correct or not. The question is : Let us ...
3
votes
1answer
115 views

Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
19
votes
1answer
1k views

Turing award papers

I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and results....
-5
votes
0answers
48 views

2 Approximation for Steiner tree

Considering the Steiner tree Problem on a complete Graph with metric distances, I am searching for a 2 approximation algorithm. Preferable with a factor better than 2.
2
votes
3answers
110 views

Is the transducer version of BPP closed under complement?

Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this ...
-4
votes
0answers
50 views

On classes $UP$ and $US$?

Is there any consequence if the classes $UP$ and $US$ have complete problems? $coNP$ is in $US$ according to https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us and does $NP$ also belong to $US$?
1
vote
0answers
53 views

What is the state of the art in first order stochastic convex optimization?

What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD? What is the optimally fastest convex function minimizing algorithm which ...
4
votes
0answers
88 views

Implementations of Dependent Type Theory

I am trying to find a minimal implementation of dependent type theory that supports Pi Types (obviously) Modules containing records Inductive data types Universe Hierarchy A notion of equality ...
-1
votes
0answers
49 views

Conjuagate operation solution

Let A,B two matrices over binary field that are similar. So there exists a solution to equation of type $$B=XAX^{-1} $$ Is there an algorithm to find all X's? If not classical, may be a quantum ...
3
votes
1answer
87 views

Complexity of unbalanced bipartite isomorphism

For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and $|B_1|=|B_2|=b$ with $a\le b$. Question. Is the problem of ...
1
vote
1answer
107 views

Extended Church's thesis and internal parametricity

I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here. Does $Internal\ parametricity \implies ECT$ hold? For forumlation of ECT see https://...
0
votes
0answers
122 views

Assuming P != NP, what is the cardinality of the set of NP-Hard languages? [closed]

Clearly if P = NP, then every non-trivial language is NP-Hard, so there are uncountably many NP-Hard languages. However, assuming P != NP is NP-Hard known to be uncountable? My guess would be yes, but ...
0
votes
0answers
47 views

Lack of atomic propositions in the Calculus of Constructions from ATTAPL textbook

I am working through the Dependent Types chapter from Advanced Topics in Types and Programming Languages (ATTAPL) by Benjamin Pierce et al. I am confused with the calculus presented Fig 2-7 (Calculus ...
-1
votes
0answers
18 views

Efficient Graph Affinity Matrix Computation

I need to compute an affinity matrix for an unweighted undirected graph of related musical artists for the purposes of spectral clustering. Now, the most obvious affinity measure to use is shortest ...
0
votes
0answers
47 views

Proposition terms vs types in Coq

Consider the following div function written in Coq. It takes in a proof that the divider is non-zero. Definition div (n d:nat) (pf: ~(d = 0)) := n/d. Focus on <...
-2
votes
0answers
39 views

What's the point of Tour Creation Algorithms for TSP if Tour Improvement ones exist? [closed]

I'm pretty new to the whole Theoretical CS stuff so forgive me if this is a stupid question. I've been researching the different basic heuristics for solving TSP, and have found that there are two ...
5
votes
2answers
120 views

How to define list zipping categorically/inductively?

Lists and fixpoints The type of $A$-lists is defined as $\mu F_A$, where $F_A(X) = 1 + A \times X$ is the "cons-or-nil"-functor and $\mu$ is the least fixpoint operator. In Haskell syntax, this would ...
1
vote
1answer
110 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 ...
4
votes
0answers
82 views

Reconstructing a colored grid with vertical and horizontal shifts

Consider the following simple problem (puzzle): given a $N \times N$ $c$-colored grid $G$ a $N \times N$ $c$-colored target grid $G_T$ a number $m$ represented in unary Can we transform $G$ into $...
-1
votes
0answers
49 views

Differences in the type signatures using dependent types

What is the difference between the following types for the $head$ function on a vector of integers. ($head$ takes a natural number $n$ and a vector $v$ of length $n$ or $(n+1)$ (depending on the ...
-1
votes
0answers
25 views

Linear programming TSP variant constraint formulation [closed]

For a variant of the TSP problem such that not all vertices have to be visited, is there a way to add a constraint such that the linear program will start at a certain vertex?
1
vote
0answers
59 views

communication complexity lower bound for computing median

In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [...
0
votes
0answers
73 views

Is ASM a regular language? [migrated]

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
-2
votes
0answers
39 views

Complexity of recognizing unit distance graphs

A Graph is Unit Distance Embeddable (UDE) if it can be embedded in the plane such that every edge has a length of 1. A minor of a UDE graph is also UDE so by the Graph Minor theorem, there must be a ...
0
votes
0answers
66 views

Does Descriptive Complexity techniques have the naturalisation barrier?

I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise? By naturalise I'm talking about the Idea of Natural ...
8
votes
1answer
311 views

PHOAS with extrinsic typing?

Parameterized Higher Order Abstract Syntax (PHOAS) is a representation of syntax trees that allows the host language's binding to be used to represent binding in the language being modelled, while ...
5
votes
1answer
241 views

Consequences of BPP=BQP

If BPP=BQP then there is a polynomial time randomized factoring algorithm. A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, ...
-2
votes
0answers
99 views

Can the aliens hustle us with Chaitin's constant?

Premise Suppose you are an alien and want to fool Earthlings you have extracted the value of Chaitin's Constant. Does the strategy below work? If so, any explicit(/basic ideas for) algorithm? If not, ...
1
vote
1answer
50 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 ...
5
votes
2answers
142 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 ...
-1
votes
0answers
24 views

Relation between bi partite graphs and neural network diagram? [closed]

I came across a bi partite graph from network flow problems in my algorithms class, the graph has a resemblance to artificial neural network diagram. Is there any relation between the two ? can ...
3
votes
0answers
78 views

The number of words of length $n$ in a context-sensitive language

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$. What is known about $s_{L}(n)$? Note that it is known that $s_{L}(n)$ is either polynomial,...
1
vote
1answer
93 views

Induction on all polynomial runtimes?

Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$? e.g.: $L\notin \...
3
votes
1answer
91 views

Term for a set that is not immune

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...
3
votes
1answer
78 views

Is there a notion of “sequential” idempotence?

TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied. Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ...

15 30 50 per page