Skip to content

Unification exponential in size of term representation #855

@UWN

Description

@UWN

(It seems linear - for this case - in the common definition of term size - did not check for refchains, though)

blam([]). blam([L|L]):-blam(L).

?- length(L,N), N>14,\+ \+ ( length(K,N),blam(L),blam(K),time(L=K) ).
% Time elapsed 0.001s, 1 Inferences, 0.001 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O], N = 15
; % Time elapsed 0.002s, 1 Inferences, 0.001 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P], N = 16
; % Time elapsed 0.003s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q], N = 17
; % Time elapsed 0.006s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R], N = 18
; % Time elapsed 0.009s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S], N = 19
; % Time elapsed 0.020s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T], N = 20
; % Time elapsed 0.030s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U], N = 21
; % Time elapsed 0.061s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U,_V], N = 22
; % Time elapsed 0.122s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U,_V,_W], N = 23
; % Time elapsed 0.245s, 1 Inferences, 0.000 MLips
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U,_V,_W,_X], N = 24
;  ... .

Metadata

Metadata

Assignees

No one assigned

    Labels

    performancePerformance enhancement

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions