A solution to SAT with virus machines with pre-computed resources

Vol.:(0123456789)
Jou nal o Memb ane Compu ing
h ps://doi.o g/10.1007/s41965-025-00190-3
RESEARCH PAPER
A solu ion oSAT wi h i us machines wi hp e‑compu ed esou ces
Da idO ellana‑Ma ín1,2· ClaudioZand on3· Albe oLepo a i3
Recei ed: 11 No embe 2024 / Accep ed: 14 Ap il 2025
© The Au ho (s) 2025
Abs ac
In Na u al Compu ing, di e en eal-li e p ocesses can appea as he inspi a ion o a new model o compu a ion. Vi us
machines use he sp ead and eplica ion o biological i uses as an inspi a ion o a model o compu a ion wi h h ee well-
di e en ia ed g aphs: he hos s g aph, ha ac s like he memo y; he ins uc ions g aph, ha ac s as a p og am; and he
ins uc ions-channel g aph, ha con ols he low o in o ma ion h ough he sys em. In p e ious wo ks, he compu a ional
powe and p oblem-sol ing capabili ies o his model ha e been demons a ed. In his wo k, we p o ide an applica ion
o sol ing he SAT p oblem in polynomial ime using an EXP-uni o m amily o supe i us machines wi h OR channel
pa allelism.
Keywo d Vi us machines, SAT p oblem, EXP-uni o m solu ion
1 In oduc ion
In he a ea o Na u al Compu ing, di e en eal-li e p o-
cesses can appea as he inspi a ion o a new model o com-
pu a ion. A pa amoun example in his espec a e Mem-
b ane sys ems (also known as P sys ems), i s in oduced
by Păun in [22], ha cons i u e a compu a ional amewo k
inspi ed by biological cells, unc ioning in a pa allel and
dis ibu ed way. These sys ems a e no ed o hei decen-
alized cha ac e is ics, wi h hei e olu ion es ablished by
he ules de ined inside di e en compa men s bounded by
memb anes.
Signi ican esea ch has been de o ed o in es iga ing his
model, conside ing many di e en aspec s. Recen s udies
ha e add essed opics such as compu a ional p ope ies [19,
21], e iciency in compu a ion [1, 13, 14], ela ionships wi h
o he o mal models, including Pe i ne s [4], mo phogene ic
sys ems [38], and Ma ko chains [35], as well as applica ions
o eal-wo ld p oblems [3, 7, 24, 39, 45]. Va ious adap a ions
o P sys ems ha e been p oposed and ho oughly examined,
such as P sys ems wi h ac i e memb anes [15, 23, 25, 37],
spiking neu al P sys ems [6, 10, 11, 16, 26, 42, 46], issue
P sys ems [20, 44], and P colonies [5, 12]. Recen esea ch
has also ocused on simula ing P sys ems using mains eam
ha dwa e [2, 41], de eloping o mal e i ica ion me hods
[17, 18], and adop ing mo e isual me hodologies [8].
In 2015, i us machines[40] we e in oduced. Besides
being a Tu ing-comple e model, o he in e es ing app oaches
ha e demons a ed hei compu a ional powe [28, 33, 34].
Thei ope a ion is inspi ed upon he way i uses sp ead
among a ious hos s and eplica e wi hin an o ganism. Such
a sp ead and eplica ion a e go e ned by a speci ic se o
ules, ope a ing on a ne wo k o in e ac ing hos s. In he las
yea s, some in e es ing applica ions o i us machines ha e
been p oposed, such as a acking c yp osys ems[27] and
modeling powe sys ems[43].
The basic a ian o i us machines, while powe ul om
a compu a ional poin o iew, is qui e ine icien , because o
i s inhe en sequen ial beha io . In ac , only one ins uc ion
is execu ed a a ime, and ha ins uc ion can only open one
single channel, ha will mo e one i us om one hos o
ano he one. To inc ease he e iciency, some a ian s ha e
been p oposed in he li e a u e, such as i us machines wi h
hos exci a ion[29], s ochas ic i us machines[31], and
mo e ecen ly, pa allel i us machines[30]. In pa icula ,
* Da id O ellana-Ma ín
[email p o ec ed]
1 Resea ch G oup onNa u al Compu ing, Depa men
o Compu e Science andA i icial In elligence, Uni e sidad
de Se illa, Se ille, Spain
2 SCORE Lab, I3US, Uni e sidad de Se illa, A da. Reina
Me cedes s/n, 41012Se ille, Spain
3 Dipa imen o di In o ma ica, Sis emis ica e Comunicazione,
Uni e si à degli S udi di Milano-Bicocca, Viale Sa ca 336,
Edi icio U14, 20126Milan, I aly
D.O ellana-Ma ín e al.
in[43] wo di e en seman ics a e applied while using chan-
nel pa allelism. On he one hand, i an ins uc ion opening
di e en channels needs a i us o pass h ough a leas one
channel o selec he pa h wi h he highes alue, hen he
i us machine is said o be using he OR seman ics. On he
o he hand, i a i us needs o pass h ough all channels
connec ed o he ins uc ion, hen he i us machine is said
o be using he AND seman ics. In his wo k, we combine
OR seman ics wi h he supe channels de ined in[32], and
we p esen an EXP-uni o m amily o so-called supe i us
machines ha sol es he SAT p oblem in linea ime wi h
espec o he numbe o a iables and clauses.
The es o he pape is o ganized as ollows. The nex
sec ion is de o ed o in oducing some no ions and no a-
ions ha a e needed o make he pape sel -con ained. In
Sec .3, he new a ian o supe i us machines combining
supe channels wi h OR seman ics will be de ined, in oduc-
ing i s compu a ional ing edien s. Sec ion4 will be de o ed
o de ining he EXP-uni o m amily o i us machines ha
sol es SAT , and o gi e an o e iew o how he p oposed
solu ion wo ks. The pape ends wi h some conclusions and
open esea ch lines o u u e wo k.
2 P elimina ies
In his sec ion, we ecall some no ions, o ix he no a ion
and o make he pape sel -con ained.
2.1 Basic no ions o se heo y and o mal language
heo y
Le
ℕ={0, 1, …}
be he se o na u al numbe s. An alphabe
Σ
is a ini e and non-emp y se o elemen s, called symbols.
An alphabe ha con ains only one symbol is called a sin-
gle on alphabe .
A mul ise o e an alphabe
Σ
is an o de ed pai
(Σ, )
such ha is a mapping om
Σ
o
ℕ
. Fo
a∈Σ
, he alue
(a) deno es he mul iplici y o symbol a in he mul ise . A
mul ise
(Σ, )
can be ep esen ed as he se
{
a
(a
1
)
1
,…,a
(a
k
)
k}
o as any pe mu a ion o he s ing
a (a
1
)
1
…a
(a
k
)
k
, wi h
ai∈Σ
and
(ai)>0
o all
1≤i≤k
. I
Σ={a}
is a single on
alphabe , hen a mul ise can simply be ep esen ed as he
s ing
a (a)
i
(a)>0
, and wi h he emp y s ing i
(a)=0
.
2.2 P oposi ional Boolean o mulas and heSAT
p oblem
A Boolean a iable x is a a iable ha can ake wo di -
e en alues, ei he 1 o 0, ha can be in e p e ed as he
logical alues ue and alse, espec i ely. A li e al is ei he
a Boolean a iable x o he nega ion o a Boolean a iable
¬x
. A clause is a disjunc ion o li e als. A p oposi ional
Boolean o mula in conjunc i e no mal o m (CNF) is a
conjunc ion o clauses. Le
Va (𝜑)={x1,…,xn}
be he se
o a iables appea ing in a p oposi ional Boolean o mula
𝜑
;
hen, a u h assignmen
𝜎
o such a o mula
𝜑
is a unc ion
𝜎∶Va (𝜑)
→
{1, 0}
ha assigns a u h alue o each a i-
able. Once each Boolean a iable has been assigned a u h
alue, clauses and o mulas can be e alua ed by in e p e -
ing he logical ope a o s in he usual way. We hus ob ain
ha a clause is sa is iable i any o i s li e als is sa is iable,
whe eas a CNF o mula is sa is iable i all o i s clauses a e
sa is iable.
SAT is an NP-comple e decision p oblem[9] ha can be
o mula ed as ollows: gi en a CNF Boolean o mula
𝜑=C1∧C2∧…∧Cm
, whe e each clause
C
j
=X
j1
∨X
j2
∨…∨X
ji
j
is he disjunc ion o li e als
X
j1
,X
j2
,…,X
ji
j
de ined o e he se o a iables
Va (𝜑)={x1,…,xn}
, de e mine whe he he e exis s an
assignmen
𝜎∶Va (𝜑)
→
{1, 0}
ha sa is ies
𝜑
.
In wha ollows, we w i e
xi∈Cj
( espec i ely,
¬xi∈Cj
)
o indica e ha he li e al
xi
( esp.,
¬xi
) appea s in he clause
Cj
.
2.3 Can o pai ing unc ion
The Can o pai ing unc ion
⟨
⋅,⋅
⟩
is a bijec i e unc ion om
ℕ2
o
ℕ
, de ined as ollows:
Fo each pai o na u al numbe s x,y, he Can o pai ing
unc ion p oduces a unique na u al numbe , hus making i
a good candida e as a size encoding unc ion, ha is, a unc-
ion ha exp esses he size o a p oblem ins ance h ough a
single alue.
2.4 EXP‑uni o m solu ions o decision p oblems
Fo mally, a decision p oblem X is a pai
(IX,𝜃X)
such ha
IX
is a language o e a ini e alphabe (whose elemen s a e
called ins ances) and
𝜃X
is a o al Boolean unc ion o e
IX
.
In he case o he S AT p oblem,
IX
is he se o s ings ha
desc ibe all possible CNF Boolean o mulas, whe eas
𝜃X
maps o ue all such o mulas which a e sa is iable.
A polynomial encoding
(cod,s)
o X is a pai o unc ions
ha can be compu ed in polynomial ime by de e minis ic
Tu ing machines, such ha o each ins ance
u∈IX
, s(u) is
a na u al numbe and cod(u) is an encoding o u o be ed as
⟨
x,y⟩=
(x+y)
⋅
(x+y+1)
2
+y
.
A solu ion oSAT wi h i us machines wi hp e-compu ed esou ces
inpu o he i us machine V(s(u)). Fo he SAT p oblem, u will
be (a s ing ep esen ing a) CNF Boolean o mula con aining
n a iables and m clauses, and we will use he Can o pai -
ing unc ion
⟨
⋅
,
⋅
⟩
as he unc ion s, so ha s(u) will be
⟨n,m⟩
.
The alue
cod(u)
will be an app op ia e encoding o he CNF
Boolean o mula u, o be ed as inpu o he i us machine
V(s(u)) = V(⟨n
,
m⟩)
.
In wha ollows, we will build uni o m amilies o i us
machines. This means ha o each possible ins ance size
s(u), he machine V(s(u)) will be able o sol e all possible
ins ances o size s(u). We will speci y he ins ance we wan
o sol e by gi ing
cod(u)
as inpu o V(s(u)), and we will
deno e he esul ing i us machine wi h he embedded inpu
by
V(s(u)) + cod(u)
.
P ecisely, we will use EXP-uni o m amilies o i us
machines o sol e he SAT p oblem. We say ha a amily
V={V(n)∣n∈ℕ}
is an EXP-uni o m solu ion o a deci-
sion p oblem
X=(IX,𝜃X)
i he ollowing condi ions hold:
• The amily
V
is exponen ially uni o m by Tu ing machines;
ha is, o each
n∈ℕ
he e exis s a de e minis ic Tu ing
machine ha wo ks in exponen ial ime wi h espec o n
and cons uc s he i us machine V(n) om n.
• The e exis s a polynomial encoding
(cod,s)
o X in
V
such
ha :
1. The amily
V
is polynomially bounded wi h espec
o
(X,cod,s)
; ha is, he e exis s a na u al numbe
k∈ℕ
such ha o each ins ance
u∈IX
, e e y com-
pu a ion o
V(s(u)) + cod(u)
akes, a mos ,
|u|k
com-
pu a ion s eps.
2. The amily
V
is sound and comple e wi h espec o
(X,cod,s)
, ha is:
– We say ha he amily
V
is sound wi h espec
o
(X,cod,s)
i o each ins ance
u∈IX
, i he e
exis s a leas one accep ing compu a ion o
V(s(u)) + cod(u)
hen
𝜃X(u)=1
.
– We say ha he amily
V
is comple e wi h espec o
(X,cod,s)
i o each ins ance
u∈IX
, i
𝜃X(u)=1
,
hen all he compu a ions o
V(s(u)) + cod(u)
a e
accep ing compu a ions.
In his sense, he amily
V
p o ides de ices loaded wi h an
exponen ial amoun o compu a ional esou ces. Since hese
esou ces a e no buil du ing compu a ion ime bu a he
while he machine V(s(u)) is being buil , we say ha he sys-
ems o such a amily
V
use p e-compu ed esou ces; ha is,
be o e s a ing he compu a ion o such de ices, a huge (in his
case, exponen ial) amoun o esou ces has been gene a ed and
can be used o sol e he p oblem.
3 Supe i us machines wi hORchannel
pa allelism
In his sec ion, we gi e he de ini ion o i us machines
when supe channels[32] and OR seman ics in channels[43]
a e conside ed. Fo simplici y, we will call he esul ing
model supe i us machines.
A pa allel i us machine wi h supe channels and OR
(channel pa allelism) seman ics, o deg ee (p,q), is a uple
whe e:
1.
Γ={ }
is a single on alphabe , whe e he only elemen
is called a i us;
2.
H={h1,…,hp}
is he se o hos s,
Hi⊆H
is he
se o inpu hos s, and
I={i
1
,…,iq}∪{#}
is he
se o con ol ins uc ions. All hese a e o de ed
se s, such ha he ollowing condi ions hold:
H∩I=�
,
∉H∪I
,
hou ∉Γ∪I
and
i1∈I
;
3.
DH=(H∪{hou },EH,wH)
is a weigh ed di ec ed g aph,
called he hos s g aph, whe e
EH⊆H×(H∪{hou })
is
such ha
(h,h)∉EH
o all
h∈H
, ou -deg ee
(hou )=0
and
wH
is a mapping om
EH
o
ℕ⧵{
0
}
;
4.
DI=(I,EI,wI)
is a weigh ed di ec ed g aph, called he
con ol ins uc ions g aph, whe e
EI⊆I×I
, ou -deg ee
(i)
≤
2
o all
i∈I
, and
wI
is a mapping om
EI
o
ℕ⧵{0}
;
5.
GC=(VC,EC)
is a di ec ed bipa i e g aph, called he
ins uc ions-channels g aph, whe e
VC=I∪EH
, being
{I,EH}
he associa ed pa i ion, and
EC⊆VC×VC
;
6.
nj∈ℕ
, o
1≤j≤p
, is he numbe o i uses ini ially
placed in hos
hj
;
7.
i1∈I
is he ini ial con ol ins uc ion, ha is, he i s
ins uc ion o be execu ed a he beginning o he com-
pu a ion;
8.
hou ∈H
is he ou pu hos , ha is, he hos in which he
ou pu is collec ed.
A pa allel i us machine wi h supe chan-
nels and OR seman ics o channel pa allelism
V= (Γ,H,Hi,I,DH,DI,GC,n1,…,np,i1,hou )
o deg ee
(p,q) can be seen as a se o p hos s, each hos
hj
con ain-
ing ini ially
nj
i uses, and a se o q ins uc ions. The hos s
a e connec ed h ough channels ha can be open o closed,
and a e ini ially closed.
EH
is de ined as
ES∪EN
, such ha
ES∩EN=�
, whe e channels om
EN
a e usual channels
whe eas channels om
ES
a e called supe channels. As
i will become clea in a momen , he di e ence be ween
he wo ypes o channels is he ollowing: while in a usual
V= (Γ,H,Hi,I,DH,DI,GC,n
1
,…,np,i
1
,hou )
D.O ellana-Ma ín e al.
channel only one i us will pass a a ime, in a supe channel
all he i uses con ained in he hos loca ed a he incoming
end o he channel will ansi . In bo h cases, he numbe o
passing i uses will be mul iplied by he weigh (a na u al
numbe ) associa ed wi h he (supe )channel. The ins uc-
ions g aph ma ks he low o he compu a ion, each ins uc-
ion ha ing he abili y o open he channels i is a ached o.
A con igu a ion o a pa allel i us machine wi h supe -
channels and OR channel pa allelism, in a speci ic momen
, deno ed
C =(n1, ,…,np, ,i ,n0, )
, is gi en by he numbe
o i uses con ained in each hos a ha momen , he cu -
en ly ac i e ins uc ion
i
, and he numbe
n0,
o i uses in
he en i onmen . The ini ial con igu a ion o V is hus gi en
by
C0=(n1,…,np,i1,0)
. I an inpu
m∈
ℕ
⧵{
0
}
is in o-
duced in a i us machine V, a numbe o ex a i uses will
be placed in he co esponding inpu hos ; we will deno e
by
V+m
he i us machine hus ob ained. A con igu a ion
is hal ing i
i =#
.
A compu a ion s ep o a i us machine V, cu en ly in
he con igu a ion
C =(n1, ,…,np, ,i ,n0, )
, will occu
as ollows. Fi s o all, he ins uc ion
i
will open all he
channels i is a ached o. F om he poin o iew o he
hos s, i a channel ( espec i ely, supe channel)
(hi,hj)
is opened, i
ni, =0
hen no i uses will pass h ough i ,
whe eas i
ni
,
>0
hen one i us ( esp.,
ni
,
i uses) will be
emo ed om he ini ial hos and
wH(hi,hj)
i uses ( esp.,
wH(hi,hj)
⋅
ni
,
i uses) will be added o he ecei ing hos
h ough he channel ( esp., he supe channel). We mus ake
in o accoun ha i k channels coming ou o he hos
hi
a e
opened, hen wo di e en scena ios may a ise: on he one
hand, i
ni
,
≥
k
, hen a i us will pass h ough each channel
and k i uses will be emo ed om such a hos ; on he o he
hand, i
ni
,
<k
, hen all he i uses will be emo ed om
ha hos and he channels whe e he i uses pass h ough
a e selec ed in a non-de e minis ic way. In[43] wo di e en
seman ics a e applied while using channel pa allelism. On
he one hand, i an ins uc ion ha opens mul iple channels
equi es a i us o go h ough a leas one channel by selec -
ing he pa h wi h he highes alue, hen he i us machine
is said o be using OR seman ics. On he o he hand, i a
i us needs o pass h ough all channels connec ed o he
ins uc ion, hen he i us machine is said o be using he
AND seman ics. F om he poin o iew o he con ol
ins uc ions, ollowing he OR channel pa allelism beha -
io desc ibed in[43], i a i us passes h ough a leas one
channel ha is opened by an ins uc ion
ij
, hen he nex
ins uc ion will be
ik
such ha
(ij,ik)∈EI
and he e is no
im∈I
such ha
(ij,im)∈EI
and
wI(ij,ik)<wI(ij,im)
; ha is,
he pa h wi h he highes alue will be selec ed. O he wise,
i he cu en ins uc ion is no a ached o any channel o i
i is a ached bu he e a e no i uses o be mo ed, hen he
pa h wi h he lowes alue will be selec ed; ha is, he nex
ins uc ion will be
ik
such ha
(ij,ik)∈EI
and he e is no
im∈I
such ha
(ij,im)∈EI
and
wI(ij,ik)>wI(ij,im)
. I he
ou -deg ee o
ij
is 2 and bo h pa hs ha e he same weigh ,
hen he ollowed pa h will be selec ed in a non-de e minis ic
way. I he ou -deg ee o
ij
is 0 hen
ij
will no ha e a nex
ins uc ion; in his case he i us machine will each a hal -
ing con igu a ion, deno ed by
i =#
.
A ansi ion o compu a ion s ep o a supe i us machine
wi h OR channel pa allelism V, om con igu a ion
C
o con-
igu a ion
C +1
, is pe o med by execu ing he ins uc ion
i
as
desc ibed abo e, and i is deno ed as
C
⇒
VC +1
(o simply
C
⇒
C +1
i V is clea om he con ex ). A hal ing compu a-
ion o a i us machine V is a ini e sequence o con igu a-
ions
C=(C0,C1,…,Cn)
, whe e
C0
is he ini ial con igu a-
ion o V, he las con igu a ion
Cn
is a hal ing con igu a ion
( ha is,
in=#
) and, o each
0≤ <n
,
C
⇒
VC +1
. A non-
hal ing compu a ion consis s o in ini ely many successi e
con igu a ions
C=(Ci∶i∈
ℕ
)
.
4 An EXP‑uni o m solu ion oSAT
In his sec ion, we p o ide an EXP-uni o m amily
V={V(k)∣k∈ℕ}
o supe i us machines wi h OR chan-
nel pa allelism, whe e each membe o he amily
V(⟨n,m⟩)
sol es all he ins ances
𝜑
o SAT wi h n a iables and m
clauses.
Le
𝜑
be an ins ance o he S AT p oblem, ha is, a CNF
Boolean o mula con aining m clauses buil o e he se
Va (𝜑)={x1,x2,…,xn}
o a iables. Le
s(
𝜑
)=⟨n
,
m⟩
be
he size o his ins ance, and le
Cod(𝜑)
be he ollowing
encoding, ha p oduces he mul ise o be gi en as inpu o
he i us machine
V(⟨n,m⟩)
o speci y ha i should sol e
he ins ance
𝜑
o SAT :
• o all
1≤i≤n
and
1
≤
j
≤
m
,
cod(𝜑)
con ains
{ }
( ha
is, one i us) in he hos wi h label (i,j, ), i he li e al
xi
occu s in clause
Cj
. He e, deno es he logical alue ue;
• simila ly, o all
1≤i≤n
and
1
≤
j
≤
m
,
cod(𝜑)
con ains
{ }
( ha is, one i us) in he hos wi h label (i,j, ), i he
li e al
¬xi
occu s in clause
Cj
. He e, deno es he logical
alue alse.
We now de ine he supe i us machine wi h OR channel
pa allelism
whe e:
1.
Γ={ },
2.
H={
⟨
i,j,
⟩
,
⟨
i,j,
⟩
,
⟨
i,j,aux
⟩
∣1≤i≤n,1≤j≤m
}∪
{⟨j,k⟩∣1≤j≤m,k∈{0, 1}n}∪
{
k
∣
k
∈{0, 1}n}∪{
yes
}
V(⟨n,m⟩) = (Γ,H,I,DH,DI,GC,n
1
,…,np,i
1
,hou ),
A solu ion oSAT wi h i us machines wi hp e-compu ed esou ces
3.
I={ ∣1
≤
≤
2n+2}∪{ o mula
j
∣1
≤
j
≤
m}∪
{assignmen s
,
ou pu
,
end}
4.
DH=(H∪{hou },EH,wH),EH=ES∪EN
E
S
= {(⟨i,j, ⟩,⟨i,j,aux⟩),(⟨i,j,aux⟩,⟨i,j, ⟩),
(⟨i,j, ⟩,⟨i,j,aux⟩),(⟨i,j,aux⟩,⟨i,j, ⟩)
EN=E1
N∪E2
N,
E1
N=E1,
N∪E1,
N,
E1,
N= {(⟨i,j, ⟩,⟨j,k⟩),(⟨i,j,aux⟩,⟨j,k⟩)
∣1≤i≤n,1≤j≤m,k∈{0, 1}n,ki=1}
E1,
N= {(⟨i,j, ⟩,⟨j,k⟩),(⟨i,j,aux⟩,⟨j,k⟩)
∣1≤i≤n,1≤j≤m,k∈{0, 1}n,ki=0}
E2
N
=(⟨j,k⟩,k),(k,yes),(yes,en )∣1≤j≤m,k∈{0, 1}n
}
w(e)=2
o
e∈ES
,
w(e)=1
o
e∈EN
5.
DI=(I,EI,wI)
E
I
= {( , +1)∣1≤ ≤2n+1}∪
{(2n+2, assignmen s),(assignmen s, o mula1
)} ∪
{( o mulaj, o mulaj+1)∣1≤j≤m−1}∪
{( o mulaj,end)∣1≤j≤m}∪
{( o mulam
,
ou pu )}
w(e)=2
o
e∈ {( o mulaj, o mulaj+1)∣1≤j≤m−1}∪
{( o mulam
,
ou pu )}
,
w(e)=1
o he wise
6.
GC=(EH∪I,EC)
E
C
= {(2 +1, (⟨i,j, ⟩,⟨i,j,aux)) ∣ 1≤i≤n,
1≤j≤m,0≤ ≤⌊n+1
2⌋}∪
{(2 ,(⟨i,j,aux⟩,⟨i,j, ⟩)) ∣ 1≤i≤n,
1≤j≤m,1≤ ≤⌊n
2⌋}∪
{(n+1+2 +1, (⟨i,j, ⟩,⟨i,j,aux))
∣1≤i≤n,1≤j≤m,0≤ ≤⌊n+1
2⌋}∪
{(n+1+2 ,(⟨i,j,aux⟩,⟨i,j, ⟩))
∣1≤i≤n,1≤j≤m,1≤ ≤⌊n
2⌋}∪
{(n+1, e)∣e∈E1,
N} ∪ {(2n+2, e)∣e∈E1,
N}
{(assignmen s,(⟨j,k⟩,k)) ∣ 1≤j≤m,k∈{0, 1}n
}∪
{( o mulaj,(k,yes)) ∣ 1≤j≤m,k∈{0, 1}n}∪
{(ou pu
,
(yes
,
en ))}
7.
ni=0
, o all
1
≤
i
≤
q
8.
hou =en
( he ou pu is sen o he en i onmen )
4.1 An o e iew o  hecompu a ion
The compu a ion o he i us machine
V(s(𝜑)) + cod(𝜑)
is
di ided in o ou s ages, ha can be desc ibed as ollows.
4.1.1 Gene a ion s age
In his s age,
2n
i uses a e going o be c ea ed in he o igin
hos s, whe e he inpu has been in oduced. Fo his pu pose,
2n+2
compu a ion s eps a e pe o med as ollows. The i s
n s eps gene a e
2n
i uses in he co esponding hos s
⟨i
,
j
,
⟩
,
in such a way ha
2n
i uses will be loca ed ei he in hose
hos s o in
⟨i
,
j
,
aux⟩
. This is ob ained h ough he applica-
ion o ules , o
1≤ ≤n
. Nex , ins uc ion
n+1
will
send a i us o each hos
⟨j
,
k⟩
in such a way ha a i us
will appea in such a hos i and only i he co esponding
u h assignmen (deno ed in he second pa o he label k)
makes ue he clause
Cj
. In he same way, he nex n s eps
a e de o ed o c ea ing
2n
i uses ei he in hos s
⟨i
,
j
,
⟩
o in
hos s
⟨i,j,aux⟩
. Since all he i uses om he p e ious ask
ha e been sen o o he hos s, we a e con iden ha hey
do no in e e e wi h hese s eps. Ins uc ion
2n+2
wo ks
simila ly o ins uc ion
n+1
, bu while he p e ious one
sends a i us o hose hos s whose u h assignmen assigns
1 o a iable
xi
, in his case, i sends a i us o hose hos s
whose co esponding u h assignmen assigns 0 o a iable
xi
. This s age akes
2n+2
s eps. The co esponding p ocess
is depic ed in Figs.1 and2.
4.1.2 Assignmen s s age
In his s age, i a hos
⟨j,k⟩
con ains a leas one i us, i
means ha he clause
Cj
is sa is ied by he co esponding
u h assignmen encoded in k. Thus, he i uses a e sen
h ough he applica ion o ins uc ion assignmen s. This
s age akes 1 compu a ional s ep. Fo his, a single s ep is
aken, ep esen ed in Fig.3.
4.1.3 Fo mula checking s age
A his poin , hos s k will ha e as many i uses as he num-
be o clauses which a e sa is ied by he co esponding u h
assignmen . I he e a e exac ly m i uses, i means ha
he co esponding u h assignmen makes ue exac ly m
clauses, hence i sa is ies he whole o mula
𝜑
. This case is
ob ained h ough he applica ion o m consecu i e ins uc-
ions
o mulaj
, o
1≤j≤m
. The seman ics o OR channel
pa allelism ensu es ha e en i one hos uns ou o i uses,
he o he hos s can s ill send hei i uses o he yes hos . In
his sense, i a leas one hos con ains m i uses, hen he
ins uc ion
o mulam
will mo e he las i us o he hos yes,
going o he ins uc ion ou pu . O he wise, a some poin , an
in e media e ins uc ion
o mulaj
will no mo e any i us,
b inging he compu a ion o he ins uc ion end. This s age
akes a mos m s eps, and i is depic ed in Fig.4.
4.1.4 Ou pu s age
I ins uc ion
o mulam
sen a i us o he hos yes, hen
he ins uc ion ou pu will be ac i a ed, and will send a
i us o he en i onmen . On he o he hand, i an ins uc-
ion
o mulaj
, o
1
≤
j
≤
m
, does no mo e any i us, hen
he e a e no u h assignmen s ha sa is y he o iginal o -
mula, and he compu a ion hal s wi hou sending any i us
o he en i onmen . This p ocess is pe o med by he module
depic ed in Fig.5.

D.O ellana-Ma ín e al.
4.1.5 Compu a ional esou ces
Fo his solu ion, he ollowing compu a ional esou ces a e
equi ed:
• Numbe o ini ial hos s:
3nm +m2n+2n+1∈O(m2n)
.
• Numbe o ini ial channels:
m
2
n+
2
nm +
2
n+1+
2
nn+
1
∈O(m
2
n+
2
n+1+n
2
n)
.
• Maximum weigh o channels:
2∈O(1)
.
• Numbe o ini ial ins uc ions:
2n+m+5∈O(n+m)
.
• Numbe o ini ial ins uc ion connec ions:
2n+2m+3∈O(n+m)
.
• Numbe o hos -ins uc ion con ol connec ions:
2mn2+m2n+1+2nn+2n+1∈O(m2n+1)
.
• Numbe o ini ial i uses (apa om hose gi en as
inpu ):
0∈O(1)
.
• Maximum numbe o compu a ion s eps:
2n+m+4∈O(n+m)
.
Fig. 1 P ocess o he gene a-
ion o he i uses needed o
he nex s age
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
h1,1, 
h1,2, 
.
.
.
h1,4, 
h2,1, 
h2,2, 
.
.
.
h2,4, 
···
···
...
···
h4,1, 
h4,2, 
.
.
.
h4,4, 
h1,1,aux
h1,2,aux
.
.
.
h1,4,aux
h2,1,aux
h2,2,aux
.
.
.
h2,4,aux
···
···
...
···
h4,1,aux

h4,2,aux

.
.
.
h4,4,aux

i1i2
···
in
−
1inin+1
hi,j,
h
j,00...
i
1...00
.
.
.
h
j,11...
i
1...11
inin+1 in+2
Fig. 2 The
2n
i uses om hos s
hi,j,
a e mo ed o he
2n
hos s
hj,k
h1,00...00
.
.
.
hm,00...00
h00...00
···
h1,11...11
.
.
.
hm,11...11
h11...11
i2n+2 iassignmen s i o mula1
Fig. 3 All he i uses co esponding o he same u h assignmen k
a e mo ed o he same hos
hk
A solu ion oSAT wi h i us machines wi hp e-compu ed esou ces
No ice ha he numbe o hos s, channels and hos -
ins uc ion con ol connec ions is exponen ial wi h
espec o he size o he inpu o mula. Al hough we
do no show i o mally, i should be clea ha he i us
machine
V(s(𝜙)) + cod(𝜙)
, in i s ini ial con igu a ion, can
be buil by a de e minis ic Tu ing machine in exponen-
ial ime wi h espec o n, he numbe o a iables in he
SAT ins ance o be sol ed. The p ecompu ed esou ces
con ained in his i us machine hen allow i o sol e he
speci ied SAT ins ance in linea ime wi h espec o he
numbe n o a iables and he numbe m o clauses. This
can be conside ed a ime-space ade-o , much like i can
be ound in Psys ems wi h ac i e memb anes[25].
4.2 An example
To exempli y he compu a ion p ocess o he p o-
posed supe i us machine, le us conside he ollow-
ing ins ance o SAT :
𝜑≡(x1∨x2)∧(x1∨¬x2)
. Since
his o mula has
n=2
a iables and
m=2
clauses,
he co esponding ecognize i us machine sol -
ing such an ins ance is
V(s(𝜑)) + cod(𝜑)
, ha is,
V(⟨
2, 2
⟩)+cod((x1∨x2)∧(x1∨¬x2))
. This ecognize
i us machine is depic ed in Fig.6, whe e a i us is in o-
duced as an inpu in hos s
h⟨
1,1,
⟩
,
h⟨
2,1,
⟩
,
h⟨
1,2,
⟩
and
h⟨
2,2,
⟩
.
In he con igu a ion
C6
, exac ly a he end o he
gene a ion s age, he numbe o i uses in he hos s
hj
,
k
(1≤j≤2, k∈{0, 1}
2)
a e desc ibed in Table1. These
numbe s ma ch exac ly he numbe o li e als ha make ue
he clause j wi h he co esponding u h assignmen k.
A he end o he assignmen s s age, only hos s
h10
and
h11
will con ain 2 i uses, ha ma ch exac ly wi h he need
o
x1
o ake he alue ue o he o mula o be sa is ied.
Since hese wo hos s ha e 2 i uses, ins uc ions
i o mula1
and
i
o mula
2
will ake he highes -weigh pa h. The e o e,
iou pu
will be selec ed and one i us will be sen o he en i on-
men , eaching a hal ing con igu a ion in he nex compu a-
ion s ep.
5 Conclusions and u u e wo k
In his wo k, an e icien (linea ime) EXP-uni o m solu-
ion o he SAT p oblem has been p esen ed by means o a
amily o supe i us machines wi h OR channel pa allelism.
This solu ion exploi s he classical schema o a b u e- o ce
algo i hm, aking ad an age o he OR channel pa allelism
p esen in his model. Taking in o accoun ha he p o ided
solu ion needs an exponen ial numbe o hos s and chan-
nels om he beginning o he compu a ion as p ecompu ed
esou ces, i would be in e es ing o look o ways o c ea e
such an exponen ial wo king space h ough o he me hods,
such as he mi osis o he hos s, like i happens wi h di ision
ules in memb ane sys ems[36].
2 2 2
h00...00
.
.
.
h11...11
hyes
iassignmen s i o mula1
···
i o mulam
iou pu
iend
Fig. 4 I he e exis m i uses in he hos
hk
, hen he ins uc ion
iou pu
will be eached. O he wise, he ins uc ion
iend
will be eached
hyes
iend iou pu
Fig. 5 I he ins uc ion
iou pu
is eached, hen we know ha he e
exis s a leas one u h assignmen ha makes he o mula ue, and
he e o e a leas one i us is p esen in he hos
hyes
D.O ellana-Ma ín e al.
Acknowledgemen s D. O ellana-Ma ín acknowledges he suppo o
he Zhejiang Lab BioBi P og am (G an no. 2022BCF05). The wo k
o A. Lepo a i and C. Zand on was pa ially suppo ed by he MUR
unde he g an “Dipa imen i di Eccellenza 2023-2027” o he Depa -
men o In o ma ics, Sys ems and Communica ion o he Uni e si y o
Milano-Bicocca, I aly.
Funding Funding o open access publishing: Uni e sidad de Se illa/
CBUA.
Open Access This a icle is licensed unde a C ea i e Commons A i-
bu ion 4.0 In e na ional License, which pe mi s use, sha ing, adap a-
ion, dis ibu ion and ep oduc ion in any medium o o ma , as long
as you gi e app op ia e c edi o he o iginal au ho (s) and he sou ce,
p o ide a link o he C ea i e Commons licence, and indica e i changes
we e made. The images o o he hi d pa y ma e ial in his a icle a e
included in he a icle’s C ea i e Commons licence, unless indica ed
o he wise in a c edi line o he ma e ial. I ma e ial is no included in
he a icle’s C ea i e Commons licence and you in ended use is no
pe mi ed by s a u o y egula ion o exceeds he pe mi ed use, you will
1
h1,1, 
1
h2,1, 
1
h1,2, 
h2,2, 
h1,1, 
h2,1, 
h1,2, 
1
h2,2, 
h1,1,aux
h2,1,aux
h1,2,aux
h2,2,aux
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
i1
i2
i3
i4
i5
i6
h1,00 h1,01 h1,10 h1,11
h2,00 h2,01 h2,10 h2,11
h00 h01 h10 h11
iassignmen s
hyes
i o mula1
i o mula2
2
iend
iou pu
2
Gene a ion
s age
Assignmen s
s age
Fo mulachecking s age
Ou pu s age
Fig. 6 The i us machine
V(⟨2, 2⟩)
wi h inpu
cod((x1∨x2)∧(x1∨¬x2))
Table 1 Numbe o i uses in
hos s
hj
,
k
a con igu a ion
C6
k00 01 10 11
j
=
1
0112
j
=
2
1021
A solu ion oSAT wi h i us machines wi hp e-compu ed esou ces
need o ob ain pe mission di ec ly om he copy igh holde . To iew a
copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
1. Alhazo , A., Lepo a i, A., Manzoni, L., Mau i, G., & Zand on,
C. (2021). Al e na i e space de ini ions o P sys ems wi h
ac i e memb anes. Jou nal o Memb ane Compu ing, 3(2),
87–96.
2. Balles e os, K. J., Cailipan, D. P. P., de la C uz, R. T. A., Caba le,
F. G. C., & Ado na, H. N. (2022). Ma ix ep esen a ion and simu-
la ion algo i hm o nume ical spiking neu al P sys ems. Jou nal
o Memb ane Compu ing, 4(1), 41–55.
3. Baque o, F., Campos, M., Llo ens, C., & Sempe e, J. (2021). P
sys ems in he ime o COVID-19. Jou nal o Memb ane Compu -
ing, 3(4), 246–257.
4. Ba yányi, P., & Vaszil, G. (2020). Desc ip ion o memb ane sys-
ems wi h ime Pe i ne s: P omo e s/inhibi o s, memb ane dis-
solu ion, and p io i ies. Jou nal o Memb ane Compu ing, 2(4),
341–354.
5. Ciencialo á, L., Csuhaj-Va jú, E., Cienciala, L., & Sosík, P.
(2019). P colonies. Jou nal o Memb ane Compu ing, 1(3),
178–197.
6. de la C uz, R. T. A., Caba le, F. G. C., Macababayao, I. C. H.,
Ado na, H. N., & Zeng, X. (2021). Homogeneous spiking neu-
al P sys ems wi h s uc u al plas ici y. Jou nal o Memb ane
Compu ing, 3(1), 10–21.
7. Díaz-Pe nil, D., Gu ié ez-Na anjo, M. A., & Peng, H. (2019).
Memb ane compu ing and image p ocessing: A sho su ey.
Jou nal o Memb ane Compu ing, 1(1), 58–73.
8. Dupaya, A. G. S., Galano, A. C. A. P., Caba le, F. G. C., De La
C uz, R. T., Balles e os, K. J., & Lazo, P. P. L. (2022). A web-
based isual simula o o spiking neu al P sys ems. Jou nal o
Memb ane Compu ing, 4(1), 21–40.
9. Ga ey, M. R., & Johnson, D. S. (1979). Compu e s and in ac a-
bili y. A guide o he heo y on NP-comple eness. W.H. F eeman
and Company.
10. Gheo ghe, M., Le ica u, R., Konu , S., Nicolescu, I., & Ado na,
H. N. (2021). Spiking neu al P sys ems: Ma ix ep esen a ion
and o mal e i ica ion. Jou nal o Memb ane Compu ing, 3(2),
133–148.
11. Ionescu, M., Păun, G., & Yokomo i, T. (2006). Spiking neu al
P sys ems. Fundamen a In o ma icae, 71(2, 3), 279–308.
12. Lange , M., & Valen a, D. (2023). On e ol ing en i onmen o
2D P colonies: An colony simula ion. Jou nal o Memb ane
Compu ing, 5(3), 117–128.
13. Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A. E., & Zan-
d on, C. (2019). Cha ac e izing PSPACE wi h shallow non-
con luen P sys ems. Jou nal o Memb ane Compu ing, 1(2),
75–84.
14. Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A. E., & Zan-
d on, C. (2020). Shallow laconic P sys ems can coun . Jou nal
o Memb ane Compu ing, 2(4), 49–58.
15. Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A. E., & Zan-
d on, C. (2020). A Tu ing machine simula ion by P sys ems
wi hou cha ges. Jou nal o Memb ane Compu ing, 2(2), 71–79.
16. Lepo a i, A., Mau i, G., & Zand on, C. (2022). Spiking neu al
P sys ems: Main ideas and esul s. Na u al Compu ing, 21(4),
629–649.
17. Liu, Y., Nicolescu, R., & Sun, J. (2020). Fo mal e i ica ion o
cP sys ems using PAT3 and P oB. Jou nal o Memb ane Com-
pu ing, 2(2), 80–94.
18. Liu, Y., Nicolescu, R., & Sun, J. (2021). Fo mal e i ica ion o
cP sys ems using Coq. Jou nal o Memb ane Compu ing, 3(3),
205–220.
19. L , Z., Yang, Q., & Peng, H. (2021). Compu a ional powe o
sequen ial spiking neu al P sys ems wi h mul iple channels.
Jou nal o Memb ane Compu ing, 3(4), 270–283.
20. Ma ín-Vide, C., Păun, G., Pazos, J., & Rod iguez-Pa on, A.
(2003). Tissue P sys ems. Theo e ical Compu e Science,
296(2), 295–326.
21. Nadiza , G., & Pie opolli, G. (2023). A g amma ical e olu ion
app oach o he au oma ic in e ence o P sys ems. Jou nal o
Memb ane Compu ing, 5(3), 129–143.
22. Păun, G. (2000). Compu ing wi h memb anes. Jou nal o Com-
pu e and Sys em Sciences, 61(1), 108–143.
23. Păun, Gh. (2001). P sys ems wi h ac i e memb anes: A acking
NP-Comple e p oblems. Jou nal o Au oma a, Languages and
Combina o ics, 6(1), 75–90.
24. Pé ez-Hu ado, I., O ellana-Ma ín, D., & Zhang, G. (2019).
P-Lingua in wo s eps: Flexibili y and e iciency. Jou nal o
Memb ane Compu ing, 1(2), 93–102.
25. Po eca, A., Lepo a i, A., Mau i, G., & Zand on, C. (2011). P
sys ems wi h ac i e memb anes: T ading ime o space. Na u al
Compu ing, 10(1), 167–182.
26. Qiu, C., Xue, J., Liu, X., e al. (2022). Deep dynamic spiking
neu al P sys ems wi h applica ions in o gan segmen a ion. Jou -
nal o Memb ane Compu ing, 4(4), 329–340.
27. Ramí ez-de-A ellano, A., O ellana-Ma ín, D., & Pé ez-Jimé-
nez, M. J. (2023). A acking c yp osys ems by means o i us
machines. Na u e Scien i ic Repo s, 13, 21831.
28. Ramí ez-de-A ellano, A., O ellana-Ma ín, D., & Pé ez-Jimé-
nez, M. J. (2023). Gene a ing, compu ing and ecognizing wi h
i us machines. Theo e ical Compu e Science, 972, 114077.
29. Ramí ez-de-A ellano, A., O ellana-Ma ín, D., & Pé ez-Jimé-
nez, M. J. (2024). B idges be ween spiking neu al memb ane
sys ems and i us machines. In e na ional Jou nal o Neu al
Sys ems, 34(06), 2450034.
30. Ramí ez-de-A ellano, A., O ellana-Ma ín, D., & Pé ez-Jimé-
nez, M. J. (2024). Pa allel i us machines. Jou nal o Memb ane
Compu ing, 6, 211–221.
31. Ramí ez-de-A ellano, A., Rod íguez-Gallego, J. A., O ellana-
Ma ín, D., & I ano , S. (2023). S ochas ic i us machines.
In: P oceedings o he 19 h B ains o ming Week on Memb ane
Compu ing, pp. 79–90. RGNC REPORT 1/2023, Se illa, Spain.
32. Ramí ez-de-A ellano, A., Valencia-Cab e a, L., O ellana-Ma -
ín, D., & Pé ez-Jiménez, M. J. Supe i us machines. In elligen
Compu ing, (submi ed)
33. Rome o-Jiménez, Á., Valencia-Cab e a, L., & Pé ez-Jiménez,
M. J. (2015). Gene a ing diophan ine se s by i us machines. In:
Bio-Inspi ed Compu ing – Theo ies and Applica ions. BIC-TA
2015. Communica ions in Compu e and In o ma ion Science,
ol. 562, pp. 331–341. Sp inge , Be lin, Heidelbe g.
34. Rome o-Jiménez, Á., Valencia-Cab e a, L., Riscos-Núñez, A.,
& Pé ez-Jiménez, M. J. (2015). Compu ing pa ial ecu si e
unc ions by i us machines. Memb ane compu ing. CMC 2015.
Lec u e no es in compu e science (Vol. 9504, pp. 353–368).
Sp inge .
35. Sempe e, J. M. (2023). Modeling Ma ko sou ces and hidden
Ma ko models by P sys ems. Jou nal o Memb ane Compu ing,
5(3), 161–169.
36. Song, B., Li, K., O ellana-Ma ín, D., Pé ez-Jiménez, M. J., &
Pé ez-Hu ado, I. (2022). A Su ey o na u e-inspi ed compu -
ing: Memb ane compu ing. ACM Compu ing Su eys, 54(1),
A icle 22.
37. Sosík, P. (2019). P sys ems a acking ha d p oblems beyond NP:
A su ey. Jou nal o Memb ane Compu ing, 1(3), 198–208.