All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Is there a self-synchronizing binary coding like Fibonacci coding but ordered well when interepreted as std binary digits?

I'm investigating a possible self-synchronizing binary encoding for use in a variable length exponent floating point format like Posits. Posits use something like Elias Gamma encoding https://en....
Pierre Houston's user avatar
1 vote
0 answers
19 views

On the power of QMA(2)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
user72910's user avatar
0 votes
1 answer
41 views

Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

Consider an $\mathit{NPO}$ problem $O = (X,L,f,\mathit{opt})$ according to the definition of $\mathit{NPO}$ found in this answer. What I don't fully understand is what happens if we use a NDTM (non-...
SmartRock's user avatar
8 votes
1 answer
112 views

Computational complexity of the elementary theory of finite fields

Let $T_f$ denote the set of first-order sentences in the language of rings which are true in all the finite fields. That is, $T_f = \{\varphi \mid K \models \varphi, \text{ for every finite field } K\}...
Reijo Jaakkola's user avatar
1 vote
0 answers
44 views

Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments

Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
Mohammad Al-Turkistany's user avatar
-1 votes
0 answers
53 views

What are some polynomials whose dft can be computed in linear time using essentially fft?

A class of such polynomials can be defined as those where the even indexed terms have the same coefficients as the odd indexed ones for each recursive step(until the remaining recursive steps are ...
user72372's user avatar
-2 votes
1 answer
42 views

How do you get enough computing power to simulate a universe in a machine smaller than a universe? [closed]

I’ve watched on a TV show that you can fit all the information in the Observable Universe in a space smaller than the Observable Universe, but does this apply to the entire universe? I have an uneasy ...
someonewhohasasanota's user avatar
0 votes
0 answers
56 views
+50

Is set cover with a fixed number of variables and an arbitrary number of constraints fixed parameter tractable?

I am an engineer who is working with some network optimization problem. After some investigation, I reallize that my problem has a form of a set cover problem but with some specific properties. $\...
Tuong Nguyen Minh's user avatar
1 vote
0 answers
12 views

improvements on maximum depth algorithm when assuming homogeneous constraints

I know of some algorithms for finding an "almost" feasible point for a linear programming problem. That is, given $n$ linear constraints $\beta_i^T x <= a_i,\beta_i\in R^d, x_i \in R^d, ...
kara890's user avatar
  • 11
1 vote
0 answers
46 views

Closed-form for exact number of iterations of binary search

(This is a cross-post from CS.SE). Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \...
Electro's user avatar
  • 111
1 vote
0 answers
129 views

Is finding the best permutation an NP-Complete problem?

We have a matrix $M$ of size $n$ by $n$ where $M[i][j] \ge 0$ and $M[i][i] = 0$. We want to create a permutation of integers $[1,\dots,N]$, like $\langle P_1, P_2,\dots,P_n \rangle$, such that $$ \...
Amir's user avatar
  • 544
-2 votes
0 answers
53 views

proof of regular language [closed]

For any language L over an alphabet Σ define twice L = {ww|w in L} for example if X={aaa,ab,bbb},twice{x}={aaaaaa,abab,bbbbbb} (1)Y=(ab)*={ε,ab,abab,ababab} show that twice(Y) is regular (2) Provide ...
I like automata's user avatar
3 votes
0 answers
61 views

Are there any programming languages based on the method of analytic tableaux, aside from Fitting's Proflog?

The method of analytic tableaux [0] describes a process by which logical formulae, particularly of first order logic, can be determined to be valid or invalid. From the Wikipedia entry: A tableau ...
jpt4's user avatar
  • 111
0 votes
0 answers
42 views

Why LOUDS is considered succinct coding?

LOUDS encoding is widely cited as succinct, e.g., in the papers, in Github repos, etc. It is straightforward that LOUDS takes 2n bits for encoding an ordered tree ...
Xavier Z's user avatar
  • 113
0 votes
1 answer
93 views

Deciding whether there are directed paths between two vertices of all possible lengths

I recently read a paper The presence of a zero in an integer linear recurrent sequence is NP-hard to decide by Blondel and Portier, in which they prove the statement The problem of determining for a ...
user918212's user avatar
1 vote
1 answer
93 views

The problem of approximating the diameter of a point set

given a set of n points P and a nxn matrix M such that for every two point u,v where M[u,v] is the distance between u and v , and the distance is pseudo metric, is there a property testing algorithem ...
adonis abboud's user avatar
1 vote
0 answers
54 views

Complexity of FirstMatch (Prefix Elimination) Operator for regular expressions

Consider the operator $\texttt{FirstMatch} : 2^{\Sigma^*} \to 2^{\Sigma^*}$ defined as follows: $$\texttt{FirstMatch}(L) = \left \{ y \mid y \in L, \forall \text{ prefixes } x \text{ of } y, x \not \...
Agnishom Chattopadhyay's user avatar
1 vote
1 answer
80 views

Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?

By binary cardinal tree, I mean a tree with degree 2. The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, this paper claims that it is possible to encode ...
Xavier Z's user avatar
  • 113
3 votes
0 answers
100 views

Why Huffman codes cannot be handled using matroid theory?

In Cormen's "Introduction to algorithms" it is stated that matroid theory cannot be applied to justify the greedy algorithm given for the construction of Huffman's codes. I was wondering ...
user1868607's user avatar
  • 1,049
0 votes
0 answers
13 views

What is a tight set for a face $F$ of the perfect matching polytope

I was reading the paper The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson, Jakub Tarnawski. There the word mentioned in many places for example Definition 4.1 `$S$ is tight set for ...
Soham Chatterjee's user avatar
-4 votes
1 answer
173 views

How to pronounce HOAS?

I am not sure if this is on-topic, but I don't think I have any hope on any English learning website. HOAS refers to higher-order abstract syntax, which is a mechanism for representing bindings using ...
ice1000's user avatar
  • 957
0 votes
0 answers
33 views

Enhancing a bipartite perfect matching solution with 1-to-2 matchings

We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest ...
Juan Ignacio Suarez's user avatar
1 vote
0 answers
148 views

Transition from Mathematics to TCS [closed]

I am an undergraduate majoring in Mathematics and I am really interested in TCS. Most of the classes I have taken are pure math classes so I was wondering: what are the core TCS courses that I should ...
Frederico Oliveira's user avatar
1 vote
1 answer
81 views

Simple Coq simplification question

I am working through Software Foundations, I had a question about the leb_refl theorem from the induction chapter. Here is my solution: ...
whatisit's user avatar
-3 votes
0 answers
44 views

Derivation of an equation [closed]

Does anyone know the derivation of the general solution of this non homogeneous equation Blockquote
Amr Bin hashim's user avatar
0 votes
1 answer
119 views

Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2

Consider a set of natural numbers $S \in \mathbb{N}^n$ for some $n \in \mathbb{N}$. Assume that each number $s_i = S^T\cdot e_i$ meets $s_i \leq 2^m$ i.e. is written on at most $m$ number of digits, ...
C Marius's user avatar
  • 141
-2 votes
0 answers
56 views

What different computational powers do I get from an oracle for an undecidable problem?

Suppose that I have got an oracle to some undecidable decision problem, say, for some language $L$. Examples include Halting problem group isomorphism problem whether a Turing machine is a busy ...
shuhalo's user avatar
  • 1,159
0 votes
0 answers
51 views

Is there optimal or approximate solution to Single-machine scheduling problem with constraints?

I'm interested in particular setup of Single-machine scheduling. I'll use the Optimal job scheduling notation to specify the situation. I'm also aware of Interval scheduling. What I want to achieve is ...
Luxter's user avatar
  • 1
2 votes
2 answers
103 views

Weighted bipartite matching with no-cycle constraint

Given a weighted bipartite graph, I need to find a maximum-weight matching with the following additional constraint: the residual graph of the chosen matching is not allowed to contain any cycles. By ...
user168715's user avatar
4 votes
0 answers
104 views

Completeness, Compactness and LST in Type Theory

I'm just getting into model theory for type theory. I would like to know: How to properly define notions Compactness in type theory? Is There Completeness, Compactness and downward Löwenheim–Skolem ...
Ember Edison's user avatar
-1 votes
0 answers
27 views

Is it possible to verify membership of black-box models in a known hypothesis class?

In verification algorithms, the output is a binary decision (Yes/No). It was shown that those algorithms are highly efficient compared to classical algorithms where the decision has more information ...
ayaxxx's user avatar
  • 120
3 votes
2 answers
114 views

How to prove that $\exists A. ~ A \times (A\to F~ A)$ encodes the greatest fixpoint of $F$?

Following Wadler's paper "Recursive types for free" and having spent some months on reconstructing the proof that $\exists A. ~ A \times (A\to F~ A)$ is the terminal $F$-coalgebra, I am ...
winitzki's user avatar
  • 542
4 votes
0 answers
73 views

Is the encoding of existential types in System F adequate?

This is somewhat related to How to encode a function from an existential type Existential types can be encoded in System F. If $P$ is any type constructor, not necessarily covariant, then the ...
winitzki's user avatar
  • 542
-2 votes
0 answers
37 views

What is TMSAS-Enumerator?

Actually, I know what is meant by enumerator according to Turing Machine topics in Automata but there are multiple observations about TMSAS. Here enumerator with context to automata and Turing ...
Supravo Biswas's user avatar
5 votes
0 answers
74 views

A split-consistency property of a formal language

I am looking for occurrences in literature of the following property of a formal language $\mathcal L$ over an alphabet $\Sigma$ For any quadruple of words $a,b,c,d\in\Sigma^*$, if $ac,bc,ad\in\...
Gejza Jenča's user avatar
1 vote
1 answer
144 views

Can the Sigma type be defined in terms of the pi type in dependent type theory?

Using the Curry-Howard Correspondence and the fact we can write: $$\forall x: f(x) \equiv \not \exists x: \lnot f(x)$$ Can we write the $\sum$ type in terms of the $\prod$ type? $$\sum(x:A)B(x) \...
zooby's user avatar
  • 113
3 votes
0 answers
83 views

How to prove that a problem is not smoothed-polynomial?

Many research works use Smoothed analysis to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is Generic-case complexity. ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
64 views

Challenges and Optimization Techniques for Translating Pratt's Certificates to CNF

I am investigating Pratt's result that Primality is in NP. This means that for a given natural number input X, there exists a CNF that is satisfiable if and only if X is a prime number. I am trying to ...
Jogenara's user avatar
  • 121
1 vote
1 answer
116 views

Where does a problem lie which is NP-hard but not QMA-hard?

I saw this complexity classes diagram in this quantum computing paper in NATURE. Based on the standard assumption of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard ...
Manish Kumar's user avatar
0 votes
0 answers
69 views

Evidence extended GCD is in $TC^0$

Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
Turbo's user avatar
  • 13k
0 votes
0 answers
50 views

Does randomness help depth?

Suppose we have a $RNC^i$ or $BPNC^i$ algorithm for a problem, is it suspected that the problem has an $NC^i$ algorithm or just an $NC^j$ algorithm for some $j\geq i$? Is there any evidence for ...
Turbo's user avatar
  • 13k
0 votes
0 answers
25 views

Efficient PTAS for 2 identical knapsacks?

Input: $v_1,v_2,...,v_n$ item profits, $0<w_1,w_2,...,w_n\leq1$ item weights. Output: $B_1,B_2$ which are subsets of $\{1,2,...,n\}$ s.t. they are disjoint, and such that $\forall i\in\{1,2\}:\sum_{...
alon's user avatar
  • 1
0 votes
0 answers
64 views

Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?

I don't have much intuition about non-uniformity so the question may be quite naive.
A. G.'s user avatar
  • 43
0 votes
0 answers
71 views

Bellman-Ford with infinite weights

I have a graph with weights of the form $a \omega + b$ where $a,b \in \mathbb{Q}$ and $ \omega$ is an infinite value, that is, a value such that for any rational number $q$, $q \le \omega$. The ...
user1868607's user avatar
  • 1,049
4 votes
1 answer
97 views

Smoothed analysis in the Turing machine model

Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
Erel Segal-Halevi's user avatar
5 votes
1 answer
206 views

Polylog-space vs NP

Let $\text{polyL} = \cup_{c} \text{SPACE}[\log^c n]$ be the set of all problems that can be solved using polylog space, what is known/believed about its relation with NP? And perhaps even PP? I'm ...
quantumrock's user avatar
0 votes
0 answers
27 views

Possibility to Use Radix Sort for Linear Sorting of Floating Point Numbers?

Radix sort is a sorting algorithm that runs in linear time because it doesn't use algebraic comparisons. Its main limitation is that, because of this, it can only sort integers. However, a 32-bit ...
Flummox's user avatar
1 vote
0 answers
55 views

How to Classify Memory Access Pattern by LLVM or Other Tools?

I am currently encountering issues with using LLVM. Here is my specific problem: I want to study the memory access patterns of applications that are suitable for mapping onto a Spatial Accelerator, ...
Chris_Wu's user avatar
2 votes
0 answers
55 views

Seeking CNF Encoding with Exponential Lower Bound in Propagation Redundancy

I'm exploring the possibility of encoding a proposition in CNF that might have an exponential lower bound for the number of steps needed to prove it unsatisfiable using propagation redundancy. While ...
Jogenara's user avatar
  • 121
1 vote
2 answers
172 views

Inconsistent Turing machine

I am reading responses to the Lucas-Penrose argument and many make sense to me. Some of them employ inconsistent Turing machines as a model of mind to escape Gödel’s first incompleteness theorem (as ...
Barney's user avatar
  • 151

15 30 50 per page
1
2 3 4 5
260